Основы теории вычилимости

ОСНОВЫ ТЕОРИИ ВЫЧИЛИМОСТИ Каждый алгоритм имеет дело с данными - входными, промежуточными и выходными. Поскольку мы собираемся уточнять понятие алгоритма, нужно уточнить и понятие данных. В качестве данных для МНР мы ограничиваемся множеством Z 0 неотрицательных целых чисел. Такое ограничение не является существенным, поскольку другие виды объектов и операции над ними могут быть закодированы натуральными числами и представлены как операции над натуральными числами. Ниже мы перечислим все команды из списка предписаний МНР (для уточнения свойства "понятность"), однозначно определим действие каждой команды (для уточнения свойства "определенность") и опишем механизм реализации алгоритма (для уточнения свойства "точность"). Машина с неограниченными регистрами является исполнителем, представляющим собой простой "идеализированный компьютер". Идеализация состоит в том, что каждый отдельный реальный компьютер ограничен как величиной чисел, которые поступают на вход, так и размером памяти (необходимой для запоминания промежуточных результатов), МНР лишена этих ограничений. Машина с неограниченными регистрами имеет неограниченно большую память, ячейки которой будем называть регистрами и Каждый регистр в любой момент времени содержит обозначать неотрицательное целое число. ... ... Рис. 3.1. Регистры МНР При этом только конечное множество регистров содержит числа, отличные от нуля. Все остальные регистры заполнены нулями. Это допущение предполагает, что каждый алгоритм использует только конечный объем памяти. В список предписаний МНР входит четыре команды: команда обнуления Z(n); команда прибавления единицы S(n); команда переадресации T(m, n) и команда условного переходам J(m, n, q). Команды обнуления, прибавления единицы и переадресации называются арифметическими. Обозначение команды Действие, производимое МНР по данной команде Z(n) S(n) T(m, n) J(m, n, q) Если , то перейти к вычислению команды алгоритма с номером q. Рис. 3.2. Список предписаний МНР Алгоритмом называется конечная непустая последовательность команд из списка предписаний МНР, начинающаяся с команды с номером 1. Производя вычисления по данному алгоритму, МНР изменяет содержимое регистров памяти в точном соответствии с командами алгоритма. Исходное состояние памяти, то есть последовательность чисел в регистрах вычислений, называется начальной конфигурацией. перед началом Предположим, что некоторый алгоритм P состоит из последовательности команд I 1 , I 2 , ..., I s . МНР начинает вычисление с команды I 1 , затем выполняются команды I 2 , I 3 и т. д. до тех пор, пока не встретится команда вида J(m, n, q). В этом случае МНР переходит к выполнению команды, предписанной J(m, n, q) и текущим содержанием регистров R m и R n Пример 3.2. Рассмотрим алгоритм P 1 I1 I2 I3 I4 I5 I6 J(1, 2, 6) S(2) S(3) J(1, 2, 6) J(1, 1, 2) T(3, 1) Применим алгоритм к следующей начальной конфигурации: R1 R2 R3 R4 R5 ... 5 3 ... Рис. 3.3. Начальная конфигурация Ход вычисления на МНР по алгоритму P 1 с начальной конфигурацией, изображенной на рисунке 3.3, можно представить, записывая последовательно сверху вниз конфигурации машины вместе со следующей командой, к которой она переходит на данном шаге. Следующая команда R1 R2 R3 R4 R5 ... 5 3 ... I1 5 3 ... I2 5 4 ... I3 5 4 1 ... I4 5 4 1 ... I5 (так как R 1 R 2 ) 5 4 1 ... I2 (так как R 1 = R 2 ) 5 5 1 ... I3 5 5 2 ... I4 5 5 2 ... I6 (так как R 1 R 2 ) (так как R 1 = R 2 ) 2 5 2 ... I7 Рис. 3.4. Вычисление по алгоритму P 1 МНР выполняет алгоритм P: I 1 , I 2 , ..., I s до тех пор, пока это возможно. Вычисление останавливается тогда и только тогда, когда нет следующей команды, то есть когда МНР только что выполнила команду I k и следующая команда в вычислении есть I v , где v > s. Это может произойти одним из способов: I) если I k = I s (выполнена последняя команда в P) и I k - арифметическая команда; 2) если I k = J(m, n, q), R m = R n и q > s. 3) если I k = J(m, n, q), R m R n и q = s. В этом случае будем говорить, что вычисление остановилось после выполнения команды I k , и заключительная конфигурации есть последовательность r 1 , r 2 , r 3 , ... содержимого регистров на этом шаге. Результатом применения алгоритма к некоторой начальной конфигурации будем считать число r 1 из регистра R 1 заключительной конфигурации. Бывают, конечно, вычисления, которые никогда не заканчиваются, например, никогда не заканчивается ни при какой начальной конфигурации вычисление по алгоритму: I 1 S(1) I 2 J(1, 1, 1) В случае, если вычислительный процесс не заканчивается получением результата, говорят, что алгоритм неприменим к начальной конфигурации. Упражнение 1. Покажите, что вычисление по алгоритму из примера 6 с начальной конфигурацией 6, 7, 0, 0, 0, ... никогда не остановится. Для удобства обозначим через P(a 1 , a 2 , ..., a n ) вычисление по алгоритму P с начальной конфигурацией a 1 , a 2 , ..., a n , 0, 0, .... Если вычислительный процесс заканчивается с результатом b, будем писать P(a 1 , a 2 , ..., a n ) = b. Определение 3.1. Пусть f - функция от n неотрицательных целых переменных со значениями во множестве Z 0 неотрицательных целых чисел (функция ). Функция f называется вычислимой на МНР (или МНР-вычислимой), если существует такой алгоритм P, что 1) вычисление P(a 1 , a 2 , ..., a n ) останавливается тогда и только тогда, когда (a 1 , a 2 , ..., a n ) принадлежит области определения f; 2) если (a 1 , a 2 , ..., a n ) принадлежит области определения f; то в заключительной конфигурации в регистре R 1 находится целое число b такое, что f(a 1 , a 2 , ..., a n ) = b. С этого момента под термином вычислимое будем подразумевать МНР-вычислимое. Рассмотрим теперь несколько простых примеров вычислимых функций. Пример 3.2. Докажите МНР-вычислимость функции x + y. Решение. Получим x + y, прибавляя y раз 1 к числу x. Начальной конфигурацией алгоритма служит x, y, 0, 0, 0, .... Типичной конфигурацией в процессе вычисления является R1 R2 R3 R4 R5 ... x+k y k ... Определим алгоритм следующим образом: I1 I2 I3 I4 J(3, 2, 5) S(1) S(3) J(1, 1, 1) Заданный алгоритм вычисляет функцию x + y. Пример 3.3. Докажите МНР-вычислимость функции Решение. Составим алгоритм для начальной конфигурации x, 0, 0, ... . Типичной конфигурацией в процессе вычисления является: R1 R2 R3 R4 R5 ... x k k+1 ... Следующий алгоритм МНР-вычисляет функцию. I1 I2 I3 I4 I5 J(1, 2, 6) S(2) J(1, 2, 6) S(3) J(1, 1, 2) I 6 T(3, 1) Упражнения 3.2. Составьте алгоритмы, вычисляющие функции: а) б) в) г) д)* е)* Здесь [x / y] означает наименьшее целое число, не превосходящее действительное число x / y. 3.3. Покажите, что для каждой команды переадресации существует программа без команд переадресации, которая на всякой конфигурации МНР дает тот же результат, что и T(m, n). Это означает, что команды переадресации на самом деле избыточны в нашем определении МНР. Тем не менее, представляется естественным и удобным иметь такие команды, облегчающие построение алгоритмов. Введем еще несколько понятий необходимых для дальнейшего изложения. Определение 3.2. n-местным предикатом на множестве M называется отображение H, сопоставляющее каждому упорядоченному набору (a 1 , a 2 , ..., a n ) элементов из M одно из логических значений "истинно" или "ложно". Пример 3.4. Функции "быть простым числом", "быть четным числом" являются одноместными предикатами на множестве целых чисел. Пример 3.5. Свойства "иметь одинаковые остатки при делении на 3" или "быть равными" являются бинарными предикатами на множестве целых чисел. Определение 3.3. Предикат характеристическая функция называется разрешимым, если его вычислима. В контексте вычислимости предикаты часто называют проблемами. Поэтому ниже мы наряду с термином "разрешимый предикат" будем использовать также "разрешимая проблема". Упражнение 3.4. Докажите разрешимость следующих предикатов на множестве целых неотрицательных чисел: а) x = y; б) ; в) x < y; г) x - четное число. За последние пятьдесят лет было предложено много математических уточнений интуитивного понятия "алгоритм". Подход, основанный на МНР, является одним из них. Между этими подходами имеются большие различия, и в то же время все эти подходы эквивалентны между собой в том же смысле, что каждое уточнение алгоритма приводит к одному и тому же классу вычислимых функций. Возникает теперь вопрос: насколько хорошо неформальное интуитивное понятие вычислимой функции отражено в различных формальных описаниях? Этот вопрос подвергался математиками серьезному обсуждению, в результате которого было высказано утверждение, известное под названием "тезис Черча": каждая функция, вычислимая посредством процесса, алгоритмический характер которого интуитивно ясен, является вычислимой функцией. Применительно к нашему изложению этот тезис можно перефразировать следующим образом: всякая функция, для которой существует алгоритм (в интуитивном смысле) вычисления ее значений, является МНР-вычислимой функцией. Сразу же заметим, что это утверждение не является теоремой, подлежащей математическому доказательству; оно имеет статус утверждения, принимаемого как постулат, справедливость которого подтверждается рядом свидетельств. Во-первых, таким свидетельством является то, что, как уже отмечалось, многие независимые уточнения интуитивного понятия вычислимой функции привели к одному и тому же классу функций. Во-вторых, никому не доводилось найти функцию, которую можно признать вычислимой в интуитивном смысле и которая не была бы МНР-вычислимой. Исходя из этих соображений и собственного опыта, большинство математиков приняли тезис Черча. 4. Нумерация программ для МНР Определение 4.1. Множество X называют счетным, если можно установить взаимно однозначное отображение Z 0 и множеством X. между множеством неотрицательных целых чисел Определение 4.2. Множество называют не более чем счетным, если оно счетно или конечно. Определение 4.3. Перечислением или нумерацией множества X называется отображение множества Z 0 на множество X. Перечисление f определяет на множестве X некоторую бесконечную последовательность элементов из X такую, что каждый из элементов множества X встречается в этой последовательности, по крайней мере, один раз. Если отображение f - взаимно однозначно, то f называют перечислением или нумерацией без повторений. Определение 4.4. Множество X называется эффективно счетным, если существует , устанавливающая взаимно однозначное соответствие между функция множествами Z 0 и X такая, что f и f--1 - вычислимые функции. Теорема 4.1. Следующие множества являются эффективно счетными: а) б) в) ; ; - множество всех конечных последовательностей целых неотрицательных чисел. Доказательство. а) Докажем сначала эффективную счетность множества , состоящего из упорядоченных пар (x, y) с целочисленными неотрицательными компонентами x и y. Геометрически это множество представляет целочисленную решетку (рис. 4.1). Рис. 4.1. Целочисленная решетка Перенумеровать точки этой решетки можно различными способами, например, так, как показано на рисунке 4.2. Рис. 4.2. Нумерация точек целочисленной решетки Предложенная нумерация устанавливает взаимно однозначное отображение между множествами процесса вычисления значений функции Черча и . Алгоритмический характер очевиден. Следовательно, по тезису - вычислимая функция. Для вычисления значений обратной функции можно, например, в соответствии с предложенным алгоритмом последовательно нумеровать точки целочисленной решетки до номера z. Пара (x, y) координат точки с номером z является значением обратной функции . По тезису Черча - вычислимая функция. Таким образом, множество эффективно счетно. б) Теперь несложно доказать эффективную счетность множества определим взаимно однозначное отображение множества троек неотрицательных целых чисел на множество и упорядоченных следующим образом . Из вычислимости функций вычислимость функций . Для этого и . Поэтому множество вытекает эффективно счетно. в) Для доказательства эффективной счетности множества всех конечных последовательностей целых неотрицательных чисел рассмотрим функцию , сопоставляющую каждому упорядоченному набору (a1, a2, ..., ak) из k неотрицательных целых чисел некоторое неотрицательное целое число. Для доказательства взаимной однозначности функции используем тот факт, что у каждого целого числа имеется ровно одно представление в двоичной системе счисления. Запишем значение функции в двоичной системе счисления: (*) Например, = = = 616 - 1 = 615; = = 2320 -1 = 2319; = 544 -1 = 543; = 520 - 1 = 519; = 3 - 1 = 2; = 32 - 1 = 31; = 1 - 1 = 0. Однозначность отображения следует из того, что . Так как, кроме того, для любого неотрицательного числа x существует, очевидно, кортеж (c1, c2, ..., cn) такой, что , то функция устанавливает взаимно и множеством однозначное соответствие между множеством Покажем, как вычисляются значения обратной функции неотрицательного числа x. . для произвольного В соответствии с формулой (*) , где - запись числа x + 1 в двоичной системе счисления. Например, ; ; ; ; ; ; ; . В силу тезиса Черча функции вычислимое множество. и вычислимы. Следовательно, - эффективно Теорема 4.2. Множество K команд МНР эффективно счетно. Доказательство. Множество K команд МНР включает четыре типа команд Z(n), S(n), T(m, n), J(m, n, q), где . Определим взаимно однозначное отображение следующим образом: = 4 (n - 1); = 4 (n - 1) + 1; ; , где - отображения, определенные в теореме 4.1. Так как функции , очевидно, вычислимы, то отсюда вытекает эффективная счетность множества K команд МНР. Теорема 4.3. Множество P всех программ для МНР эффективно счетно. Доказательство. Пусть - произвольная программа для МНР. Определим взаимно однозначное отображение следующим образом: . где - отображения, определенные в теореме 4.1. Так как функции , очевидно, вычислимы, то отсюда вытекает эффективная счетность множества P всех программ для МНР. Разумеется, существует много других отображений из P в , устанавливающих эффективную счетность множества P. Для нашего изложения подходит любое из таких отображений. Зафиксируем одно из них, например, то которое описано в теореме 4.3. Определение 4.5. Число (P) называется геделевым номером программы P или просто номером программы P. Отображение играет важную роль в теории алгоритмов. Название числа (P) связано с именем К. Геделя, впервые в 1931 году предложившего идею кодирования нечисловых объектов натуральными числами. Ниже программу P с геделевым номером n будем обозначать при однозначности отображения следует . Из взаимной , хотя обе эти программы могут вычислять одну и ту же функцию. Пример 4.1. Найдем геделев номер программы P: , , вычисляющей функцию f(x) = x + 2. . (S(1)) = 4 (1 - 1) + 1 = 1; . Пример 4.2. Вычислим программу по ее геделеву номеру m. 1) m = 0. ; . Следовательно, : 1. Z(1). 2) m = 1. ; . Следовательно, : 1. S(1). 3) m = 2. ; . и Следовательно, : 1. Z(1), 2. Z(1). 4) m = 3. ; . Следовательно, : 1. T(1, 1). Заметим, что различные программы и вычисляют одну и ту же функцию f(x) = 0. 5. Нумерация вычислимых функций Определение 5.1. Пусть f - n-местная функция, вычислимая по программе P с геделевым номером m = (P). Число m будем называть индексом функции f. Вычислимую функцию от n переменных с индексом m будем обозначать символом . Из определения 5.1 следует, что каждая n-местная вычислимая функция f представлена в перечислении Ниже мы в основном будем рассматривать одноместные вычислимые функции простоты в их обозначении верхний индекс будем опускать. . Для Упражнение 5.1. Докажите, что у каждой вычислимой функции имеется бесконечно много индексов. Приступим теперь к доказательству теоремы о существовании невычислимых функций. Идея доказательства этой теоремы столь же важна, как и результат. Теорема 5.1. Существует невычислимая всюду определенная функция. Доказательство. Пусть Положим - некоторое перечисление всех вычислимых функций: Функция g отличается от любой вычислимой функции функция определена в точке n, то в точке n. Действительно, если . Если не определена в точке n, то g тем, что значение g(n) определено. Таким образом, отличается от следовательно, g - невычислимая всюду определенная функция. и, Метод построения функции в теореме 5.1 является примером диагональной конструкции, открытой Кантором. Лежащая в его основе идея является центральной в доказательстве большинства результатов, связанных с вычислимостью функций, и применима к огромному числу ситуаций, возникающих в различных разделах математики. Поясним, почему для примененного в теореме 5.1 метода выбран термин диагональный. Для этого проиллюстрируем метод построения функции g с помощью следующей бесконечной таблицы: 1 2 3 ... ... ... ... ... ... ... ... ... ... ... Рис. 5.1. Диагональная конструкция При построении функции g для определения значений в точках n выбирались диагональные элементы таблицы . Выбранные значения изменялись так, чтобы обеспечить отличие g(n) от . Очевидно, что новые значения функции можно выбирать сравнительно свободно. Например, функция является другой невычислимой всюду определенной функцией. Проиллюстрируем диагональную конструкцию на примере из теории множеств. Пример 5.1. Докажем, что множество всех подмножеств множества перечислить (перенумеровать). От противного, пусть нельзя - перечисление всех подмножеств множества Определим новое подмножество B множества следующим образом: . . Очевидно, , что противоречит предположению. Поэтому множество всех подмножеств множества перечислить. нельзя Из доказанного вытекает, что множество всех подмножеств множества несчетно. Упражнения 5.2. Используя диагональный метод, докажите что множество всех функций из N в N несчетно (Кантор). 5.3. Докажите, что множество всех невычислимых всюду определенных функций из N в N несчетно. 6. Универсальные программы В этом разделе мы докажем несколько неожиданный результат, состоящий в том, что существуют универсальные программы, то есть программы, которые в некотором смысле реализуют все другие программы. Этот результат является одним из основных результатов теории вычислимости. Определение 6.1. Универсальной функцией для n-местных вычислимых функций называется (n+1)-местная функция . Для примера рассмотрим функцию вычислимые функции целого числа т функция . Эта функция реализует все одноместные . Действительно, для произвольного неотрицательного совпадает с функцией . Таким образом, название функции одноместных функций. вполне соответствует классу вычисляемых ею Ниже для простоты вместо будем писать . Теорема 6.1. Для каждого натурального числа n универсальная функция вычислима. Доказательство. Покажем, как можно вычислить значение функции для заданного числа m и фиксированного набора (x 1 , ..., x n ). Неформальная процедура вычисления значения состоит в следующем: "Декодируйте число m и восстановите программу Р m . Затем имитируйте вычисление по этой программе. Если вычисление по программе заканчивается, требуемое значение содержится в регистре R 1 ". По тезису Черча заключаем, что функция Определение 6.2. Любая программа Р(n), вычисляющая функцию универсальной программой. вычислима. , называется Универсальные программы полностью соответствуют своему названию. Действительно, так как универсальная программа Р(n) позволяет вычислить любую n-местную вычислимую функцию, то, по сути дела, программа Р(n) заменяет абсолютно все программы для вычисления n-местных функций. Проиллюстрируем теперь, как использовать вычислимость универсальных функций в диагональных построениях. 7. Алгоритмически неразрешимые проблемы Основным стимулом, приведшим к выработке понятия алгоритма и созданию теории алгоритмов, явилась потребность доказательства неразрешимости многих проблем, возникших в различных областях математики. Специалист, решая задачу, всегда должен считаться с возможностью того, что она может оказаться неразрешимой. При доказательстве неразрешимости той или иной проблемы часто используется так называемый метод сводимости, заключающийся в следующем. Пусть, например, в результате некоторых рассуждений удалось показать, что решение проблемы Pr1 приводит к решению другой проблемы Pr2. В этом случае говорят, что проблема Pr2 сводится к проблеме Pr1. Таким образом, если проблема Pr2 сводится к проблеме Pr1, то из разрешимости Pr1 следует разрешимость Pr2 и, наоборот, из неразрешимости Pr2 следует неразрешимость Pr1. В данном разделе метод сводимости используется при доказательстве теоремы 7.3. Ниже доказывается неразрешимость ряда известных проблем. Теорема 7.1. Проблема "функция всюду определена" неразрешима. Доказательство. Пусть g - характеристическая функция этой проблемы Нам надо показать, что функция g невычислима. От противного, предположим, что g - вычислимая функция. Рассмотрим функцию Функция f всюду определена и отличается от каждой вычислимой функции Применяя g и универсальную функцию Из вычислимости функций g и . , запишем f в виде: по тезису Черча следует вычислимость функции f. Полученное противоречие доказывает невычислимость функции g. Таким образом, проблема "функция всюду определена" неразрешима. Обозначим область определения через и и множество значений функции соответственно. Теорема 7.2. Проблема " " неразрешима. Доказательство. Характеристическая функция этой проблемы задается следующим образом: Предположим, что функция g вычислима, и приведем это предположение к противоречию. Рассмотрим функцию Так как функция g вычислима, то по тезису Черча функция f также вычислима. С другой стороны, для любого x область определения Dom(f) функции f отлична от области определения , и, следовательно, . Таким образом, предположение о вычислимости характеристической функции g неверно. Поэтому проблема " " неразрешима. Замечание 7.1. Доказанная теорема вовсе не утверждает, что мы не можем для любого конкретного числа a сказать, будет ли определено значение . В теореме лишь утверждается, что не существует единого общего метода решения вопроса о том, будет ли значение определено. Замечание 7.2. Проблему " " называют также проблемой самоприменимости. Такое название связано с формулировкой проблемы в форме: "Остановится ли МНР, работая по программе с начальной конфигурацией (x)?". Другими словами: "Применима ли программа к своему кодовому номеру?". Теорема 7.3. Проблема " " неразрешима. Доказательство. Если бы проблема " более простая проблема " " была разрешима, то была бы разрешима ", что противоречит доказанной выше теореме. Замечание 7.3. Доказанную теорему часто интерпретируют как утверждение о неразрешимости проблемы остановки, в которой говорится, что не существует общего метода, устанавливающего, остановится ли некоторая конкретная программа, запущенная с некоторым конкретным набором начальных данных. Смысл этого утверждения для теоретического программирования очевиден: не существует общего метода проверки программ на наличие в них бесконечных циклов. В доказательстве теоремы мы показали, что проблема остановки " ", по крайней мере, не проще, чем проблема самоприменимости " ". Мы свели вопрос о неразрешимости одной проблемы к другой. Это прием часто используется при доказательстве неразрешимости проблем. 8. s-m-n-теорема В этом разделе мы докажем теорему, принадлежащую к числу основных результатов теории алгоритмов. Суть теоремы в следующем. Допустим, что f(х, у) - вычислимая функция. Для каждого фиксированного значения a переменной х функция f порождает одноместную вычислимую функцию g a (y) = f(a, у). Из вычислимости функции g a следует существование индекса b такого, что f(a, у) = f b (у). Оказывается индекс b можно эффективно вычислить по параметру а. Теорема 8.1 (s-m-n-теорема, простая форма). Пусть f(х, у) -вычислимая функция. Существует всюду определенная вычислимая функция s(x), такая, что f(х, у) = f s(x) (у). Доказательство. Из вычислимости функции f(х, у) следует существование МНРпрограммы Pr, которая, исходя из начальной конфигурации (x, y, 0, 0, ...), вычисляет значение функции f от двух аргументов х и у. Изменим программу Pr, добавив спереди команды, преобразующие начальную конфигурацию R1 R2 R3 R4 ... y ... (*) в конфигурацию R1 R2 R3 R4 ... a y ... следующим образом: T(1, 2) Z(1) Pr Новая программа Pr1, примененная к начальной конфигурации (*), вычисляет значение функции g a (y) = f(a, у) от одного аргумента у. Теперь рассмотрим функцию s(a) = (Pr1), сопоставляющую произвольному неотрицательному целому числу a геделев номер программы Pr1. Функция s всюду определена и по тезису Черча вычислима. Кроме того, по построению f s(a) (у) = f(a, у) для каждого . Замечание 8.1. Сформулированную теорему называют также теоремой параметризации, поскольку она позволяет по заданной вычислимой функции f(x, у) и фиксированному параметру a найти геделев номер s(a) программы, вычисляющей функцию f s(a) (у) = f(a, у). Доказанная выше теорема 8.1 является частным случаем более общей теоремы. Теорема 8.2 (s-m-n-теорема). Пусть m, n - натуральные числа, вычислимая функция с геделевым номером a. Существует всюду определенная вычислимая функция - такая, что . Доказательство сформулированного утверждения аналогично доказательству теоремы 8.1. Замечание 8.2. Название теоремы 8.2 связано с обозначением формулировке теоремы. для функций в Покажем теперь, как можно использовать s-m-n-теорему для доказательства неразрешимости проблем. s-m-n-теорема часто используется для сведения проблемы " " к другим проблемам. Теорема 8.3. Проблема " " неразрешима. Доказательство. Рассмотрим функцию По тезису Черча функция f(x, y) вычислима. Отсюда по s-m-n-теореме вытекает существование всюду определенной вычислимой функции s(x) такой, что . По определению функции f(x, y) имеем: . Следовательно, истинность условия можно установить, определив справедливость равенства . Тем самым мы свели проблему " " к проблеме " Поскольку первая из них неразрешима, то неразрешима и вторая. ". Замечание 8.3. Теорема 8.3 показывает, что в области проверки правильности компьютерных программ имеются принципиальные ограничения. В ней говорится о том, что не существует алгоритма проверки того, будет ли программа вычислять нулевую функцию. Несколько изменив доказательство теоремы 8.3, можно убедиться в том, что то же самое справедливо и для любой другой конкретной вычислимой функции. Теорема 8.4. Проблема неразрешима. Доказательство. Допустим, что проблема проблема разрешима. Тогда разрешима и , где c - индекс функции 0 8.3. Таким образом, проблема . Однако, это противоречит теореме неразрешима. Замечание 8.4. Из теоремы 8.4 следует, что вопрос о том, вычисляют ли две программы одну и ту же одноместную функцию, неразрешим. Важность этого результата для теоретического программирования очевидна. Упражнения 8.1. Докажите, что не существует алгоритма, определяющего по тексту программы, будет ли эта программа вычислять некоторую конкретную вычислимую функцию. 8.2. 2. Покажите, что не существует всюду определенной вычислимой функции f(x, y), обладающей следующим свойством: если программа происходит за f(x, y) или меньше шагов. останавливается, то это Указание. Покажите, что если бы такая функция существовала, то проблема остановки была бы разрешима. Естественно задаться вопросом, какие свойства вычислимых функций можно алгоритмически распознать по их программам. Оказывается, что никакие, кроме тривиальных. Доказательство этого факта содержится в теореме Райса. Теорема 8.5 (теорема Райса). Пусть B - непустое множество одноместных вычислимых функций, не совпадающее со всем множеством Тогда проблема " одноместных вычислимых функций. " неразрешима. Доказательство. Очевидно, что проблема " разрешима проблема " нигде не определенная функция Выберем некоторую функцию " разрешима тогда и только тогда, когда ". Поэтому без потери общности можно считать, что не принадлежит B. и рассмотрим функцию По тезису Черча функция f(x, y) вычислима. Поэтому существует (по s-m-n-теореме) всюду определенная вычислимая функция s(x) такая, что определению функции f(x, y) имеем: . По . Таким образом, с помощью вычислимой функции s(x) мы свели проблему " проблеме " ". Следовательно, проблема " "к " неразрешима. Дадим более содержательную формулировку теоремы Райса. Пусть Q некоторое свойство одноместных вычислимых функций. Свойство Q назовем нетривиальным, если существуют функции, обладающие свойством Q, и функции не обладающие этим свойством. Все обычно рассматриваемые свойства являются нетривиальными. Примерами нетривиальных свойств служат следующие: • • • • • функция тождественно равна нулю; функция нигде не определена; функция всюду определена; функция взаимно однозначна; функция определена при x = 0. Так как вычислимые функции могут быть заданы программами их вычисления, то естественно возникает вопрос: можно ли по программе узнать, обладает ли соответствующая ей функция заданным нетривиальным свойством. Теорема 8.6. Каково бы ни было нетривиальное свойство Q одноместных вычислимых функций, задача распознавания этого свойства алгоритмически неразрешима. Доказательство. Пусть B - множество одноместных вычислимых функций, обладающих свойством Q. Множество B не пусто и не совпадает со всем множеством одноместных вычислимых функций. По теореме Райса проблема " " неразрешима. Из последней теоремы следует неразрешимость многих задач, связанных с программированием. Например, если имеется некоторая программа, то по ней, вообще говоря, ничего нельзя сказать о функции, реализуемой программой. По двум программам нельзя установить, реализуют ли они одну и ту же функцию, а это приводит к неразрешимости многих задач, связанных с эквивалентными преобразованиями и минимизацией программ. В любом алгоритмическом языке, какие бы правила синтаксиса там ни применялись, всегда будут иметься "бессмысленные" программы, задающие функции не определенные ни в одной из точек (эти программы нельзя обнаружить). Теорема Райса позволяет доказывать алгоритмическую неразрешимость многих задач, связанных с вычислениями на компьютерах. Более подробно ознакомиться с формальными подходами к вычислимости можно по книгам [4, 5]. ЛИТЕРАТУРА 1. Основы информатики и вычислительной техники. Пробное учебное пособие для средних учебных заведений. Ч. 1. Под ред. А. П. Ершова и В. М. Монахова. - М: Просвещение, 1985. 2. Ершов А. П. Алгоритмический язык . - Наука и жизнь. - 1985. - №11. - С. 61-63. 3. Абрамов С. А. Математические построения и программирование. - М.: Наука, 1978. 4. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. - М.: Мир, 1983. 5. Трахтенброт В. Л. Алгоритмы и вычислительные автоматы. - М.: Советское радио, 1974.