A08DPPMAT_UPS2006D00

ТЕОРЕМА 11.3. Проблема x Dx алгоритмически неразрешима.

Доказательство. Предположим противное. Тогда существует алгоритм A, который для любого x N выясняет, верно или нет x Dx.

Для получения противоречия построим функцию g x , где

g x 0, если x Dx, (11.7)

не определена , если x Dx.

Функция g x вычислима. Алгоритм ее вычисления следующий. Инструк-

циями алгоритма A, выясним, что именно верно: 1) x Dx или 2) x Dx. Теперь к A добавляем новые инструкции: если 1), то g x 0 и алгоритм останавливается, если 2), то алгоритм зацикливается.

Поскольку функции g x вычислима, а в последовательности (11.3)

Случай 1), m Dm. Так как Dm — область определения функции φm, то φm m существует. А по (11.8) φm m не существует, противоречие.

Случай 2), m Dm. Тогда φm m не существует. Однако по (11.8) φm m 0, противоречие. Итак, искомого алгоритма A не существует.

Теорема доказана.

Проблема остановки МНР. Пусть Mx — произвольная МНР. Поместим в ее регистры некоторые данные y и запустим машину. После длительной работы машины у нас возникает подозрение, что машина M никогда не остановится. Для того, чтобы быть уверенным в остановке машины нужно располагать алгоритмом A, который по машине M и начальному содержимому ее регистров определяет, остановится машина M или

данными программами. Пусть φ0, φ1, φ2, . . . — соответствующие унарные функции, которые вычисляют данные машины.

Пусть стартует машина Mx, имея начальное значение регистра R1, равное y (начальные данные). Нам по x и y нужно установить, произойдет ли остановка машины.

111

ТЕОРЕМА 11.4. Не существует алгоритма, который по машине Mx и ее начальным данным y определяет, остановится или нет машина Mx.

Доказательство. Предположим противное. Пусть искомый алгоритм A существует.

Рассмотрим функцию g x, y , где

0, если φx y не существует.

Слова «φx y существует» можно заменить на слова «машина Mx с на-

чальными данными y остановится». Слова «φx y не существует» означают «машина Mx с начальными данными y не остановится». Если алгоритм A выявил факт, что машина Mx с начальными данными y остановится, то выходным объектом считаем число 1. Если алгоритм A выявил факт, что машина Mx с начальными данными y не остановится, то выходным объектом считаем число 0.

Следовательно, можно считать, что алгоритм A вычисляет функцию g x, y . Поэтому функция g x, y вычислима. Тогда вычислима функция

существует, т.е. x Dx.

Мы получили существование алгоритма для определения включения x Dx. Это противоречие, т.к. по предыдущей теореме проблема x Dx алгоритмически неразрешима.

Теорема доказана.

Теорема Райса. Мы привели два примера алгоритмически неразрешимых проблем. Укажем богатый источник неразрешимых проблем, связанный с нумерациями функций. Рассмотрим множество

всех унарных вычислимых функций. Пусть K — подмножество во множестве F, отличное от пустого множества и самого множества F, т.е.

K F и K F.

112

В перечислении (11.10) каждая функция имеет какое-то множество номеров, в частности, каждая функция из K имеет множество номеров. Объединение всех множеств номеров функций из K обозначим через A. Поэтому

An N φn K .

Поставим вопрос о разрешимости множества A. Если множество A разрешимо, то существует алгоритм A, который по номеру n функции φn отвечает «да» или «нет» на вопрос φn K . Следующая теорема утверждает невозможность такого алгоритма.

ТЕОРЕМА 11.5 (Райс). Пусть K — подмножество во множестве F всех унарных вычислимых функций, причем K F. Пусть A — множество всех номеров функций из K . Тогда множество A неразрешимо.

Доказательство. Пусть f — нигде не определенная унарная функция. Возможны два случая: 1) f K , 2) f K .

Рассмотрим случай 1), т.е. f K . Так как K F, то существует функция g x F K . Зададим бинарную функцию f n, x правилом

Покажем, что функция f n, x вычислима. Алгоритм A для ее вычисления

получается соединением инструкций для φn n U n, n с инструкциями для g x . Вычисляем φn n . Если число φn n существует, то инструкциями для вычисления функции g x находим число g x . Если число φn n не существует, то A работает бесконечно, перехода к вычислению g x нет.

Итак, функция f n, x вычислима. Применим теорему о параметризации. Получим одноместную, всюду определенную вычислимую функцию

не определено, если число φn n не определено.

Для n N возможны случаи а) φn n определено, б) φn n не определено.

В случае а) (когда φn n существует) из (11.12) получаем равенство функций φk n x g x . По условию g x F K . Поэтому

k n A.

113

В случае б) (когда φn n не существует) получаем равенство функций φk n x f x . При этом f K . Поэтому

Из этого условия получаем: если множество A разрешимо, то разрешимо множество K. Однако K неразрешимо, значит и множество A неразрешимо.

Итак, мы доказали неразрешимость множества A в случае 1) f K . Рассмотрим случай 2) f K . Тогда f F K . По случаю 1) множество F K неразрешимо. Тогда неразрешимо его дополнение в F, т.е.

неразрешимо множество A, что и нужно. Теорема доказана.

Проблема самоприменимости. Пусть A — нормальный алгорифм в алфавите A со схемой Z. Слово P , поступающее на вход алгорифма A, должно быть словом в алфавите A . Символы и не содержатся в алфавите A . Поэтому формулы подстановок в схеме Z не являются словами алфавите A и не могут поступать на вход алгорифма A.

Рассмотрим новый способ записи схемы Z в алфавите A . Он основан на следующей идее. Вместо произвольного алфавита A a1, . . . , an в математике можно использовать алфавит A0 a, b из двух букв. Действительно, можно изобразить буквы a1, . . . , an алфавита A следующим способом:

114

Слово P — код слова P в алфавите A0. Обратно, по коду (11.15) легко восстанавливается само слово P в алфавите A . Это замечание показывает, что для всех наших рассмотрений в принципе достаточно алфавита

A0 a, b .

Пусть A — нормальный алгорифм в алфавите A a1, a2, . . . , an , где n 2. При работе этого алгорифма учитываем, что все слова P в алфавите A можно закодировать в алфавите

A0 a, b , где a a1, b a2.

Для букв и также можно ввести их изображение в алфавите A0. Поэтому формулы схемы Z можно изобразить словами в алфавите A0.

Введем понятие изображение алгоритма A. Для произвольного алгоритма — это конструктивный объект, например, натуральное число или слово, содержащий в себе полную информацию об алгоритме A.

Опишем изображение алгоритма в случае нормального алгорифма. Пусть A — нормальный алгорифм.

Изображение AИ алгорифма A получается так. Вводим новую букву γ, закодированную словом в алфавите A0. Мы будем сцеплять формулы подстановок в одно слово, и эта буква будет служить в качестве разделителя формул подстановок. Схема Z является упорядоченной последовательностью формул подстановок

в одно слово. Для этого берем вначале код формулы u1 v1 и справа к нему приписываем код буквы γ. Получаем слово в алфавите A0 a, b . К нему справа приписываем формулу u2 v2, затем букву γ и т.д., пока не закончатся формулы подстановок. Получим слово P в алфавите A0 a, b , которое называется изображением нормального алгорифма A и обозначается через AИ.

Поскольку слово P AИ является словом в алфавите A0 a, b A , то мы можем предъявить это слово на вход нормального алгорифма A. При этом возможны следующие два случая 1) и 2).

115

1)Алгорифм A перерабатывает слово P в некоторое слово Q и останавливается. Мы выражаем этот факт словами «алгорифм A применим к своему изображению».

2)Алгорифм A работает до бесконечности, и результата переработки A P нет. Этот факт выражается словами «алгорифм A неприменим к своему изображению».

ОПРЕДЕЛЕНИЕ 11.4. Алгорифм A называется самоприменимым, если он применим к своему изображению AИ.

В противном случае алгорифм A не самоприменим. Тем самым алгорифм A самоприменим, если, получив на входе свое изображение P AИ, он переработает P в некоторое слово Q. Приведем примеры самоприменимых и несамоприменимых алгорифмов.

ПРИМЕР 11.1. Пусть A — тождественный алгорифм. Он переработает любое слово P в слово P . Поэтому он применим к любому слову, в частности к слову P AИ.

Поэтому тождественный алгорифм самоприменим.

ПРИМЕР 11.2 . Пусть A — пустой алгорифм. Он неприменим к любому слову, в частности к слову P AИ.

Поэтому пустой алгорифм несамоприменим.

Поставим следующую задачу. Мы имеем алгорифмы, которые разделены на два типа: самоприменимые и несамоприменимые. Нам хотелось бы иметь способ для определения по записи алгорифма A, какой случай имеет место. Тем самым возникает следующая алгоритмическая проблема самоприменимости.

Необходимо найти алгоритм B, который, получив на входе запись произвольного алгорифма A ответит на вопрос: «алгорифм A самоприменим или нет?».

Как нам получить ответы «да» или «нет»? Договоримся, что если результат переработки слова P (т.е. некоторое слово Q) — пустое слово, то это означает ответ «да». Если результат переработки слова P является непустым словом, то это означает ответ «нет».

Сформулированная выше задача алгоритмически неразрешима.

ТЕОРЕМА 11.6 . Не существует алгоритма B для определения самоприменимости.

Доказательство в [16].

116

Упражнения к лекции 11

ЗАДАЧА 1. Пусть A1 и A2 — подмножества во множестве E. Предположим, что A1 и A1 — разрешающие методы для подмножеств A1 и A2. Какие инструкции содержатся в разрешающем методе для следующих подмножеств:

1 A1 A2, 2 A1 A2, 3 A1 A2 ?

ЗАДАЧА 2. Построить примеры двух различных МНР программ, которые вычисляют одну и ту же унарную функцию.

ЗАДАЧА 3. Построить пример бесконечного множества различных МНР программ, которые вычисляют одну и ту же унарную функцию.

ЗАДАЧА 4. Указать два различных числа a и b и унарные функцию φa и φb, для которых φa φb.

ЗАДАЧА 5. Привести пример функции φa и бесконечного множества номеров b, для которых φb φa.

ЗАДАЧА 6. Пусть a — некоторое натуральное число и

A b N φb φa .

Верно ли, что множество A неразрешимо?

ЗАДАЧА 7. Рассмотрим алгоритм B, который, получив на входе запись P AИ произвольного алгоритма A, перерабатывает P в выходное слово тогда и только тогда, когда алгоритм A несамоприменим. Тем самым имеем следующее условие.

Алгоритм B применим к записи A тогда и только тогда, когда алгоритм A несамоприменим.

Показать, что не существует указанного алгоритма B.

117

Рассмотрим кодирование произвольного алфавита A с помощью алфавита из двух букв a, b . Изобразим буквы a1, . . . , an алфавита A следующим способом:

a1 aba, a2 abba, a3 abbba, . . . , an a b . . . b a.

n раз

ЗАДАЧА 8. 1 Найти коды следующих слов:

u1 a2a1a2, u2 a2a2, u3 a1a1a3.

2 Определить слово в алфавите A по его коду:

ЗАДАЧА 9. Нормальный алгорифм A в алфавите a1, a2, a3 имеет схему вида

a1 a1

a2 a3

Закодировать символы алфавита a1, a2, a3 в алфавите a, b . Затем закодировать символ , разделитель слов γ и построить изображение AИ нормального алгорифма A.

ЗАДАЧА 10. Является ли алгорифм A из предыдущей задачи самоприменимым?

118

Лекция 12. Алгоритмические проблемы в логике и математике

Алгоритмические проблемы, рассмотренные в предыдущей лекции, относятся к самой теории алгоритмов. Наиболее интересны те алгоритмические проблемы, которые возникают в других дисциплинах: математической логике, алгебре и теории чисел. Рассмотрим такие проблемы.

Во вводном курсе математики рассматривались формулы алгебры высказываний. Они образованы из переменных X, Y, . . . и логических знаков !, ", , #, с помощью нескольких правил образования формул. Более строго эти правила рассматриваются в курсе математической логики [10], где построение исчисления высказываний осуществляется в виде формальной системы.

Примерами формул являются следующие выражения:

F1 X " Y X # Z , F2 X # X.

Вторая из этих формул является тождественно истинной формулой, т.е. принимает значение «истина» при всех значениях входящих в нее букв. Тождественно истинные формулы играют важную роль в логике. Поэтому возникает следующая задача. Требуется найти алгоритм, с помощью которого для произвольной формулы F алгебры высказываний можно выяснить ее тождественную истинность. Тем самым у нас имеется следующая алгоритмическая проблема.

Проблема разрешимости для исчисления высказываний. Пусть

E— множество всех формул алгебры высказываний, A— множество всех тождественно истинных формул. Найти алгоритм для определения, будет ли формула F E содержаться во множестве A или нет.

Эта проблема имеет положительное решение. Действительно, искомый алгоритм существует. Он заключается в нахождении таблицы истинности и проверке того, что во всех ее клетках, где вписываются значения формулы, получено значение «истина».

Проблема разрешения для исчисления предикатов. Рассмотрим аналогичную задачу для исчисления предикатов. Проблема разрешимости в исчислении предикатов ставится так же, как и в исчислении высказываний: существует ли алгоритм, позволяющий для любой формулы F исчисления предикатов установить, является ли она тождественно истинной.

119

ТЕОРЕМА 12.1 . (А.Черч, 1936 г.). Не существует алгоритма, позволяющего для произвольной формулы F исчисления предикатов установить, является ли она тождественно истинной или нет.

Тем самым аналогичная задача для исчисления предикатов алгоритмически неразрешима.

где f x1, x2, . . . , xn — многочлен от n переменных с целыми коэффициентами. Такие уравнения называются диофантовыми в честь греческого математика Диофанта.

Простейшее из таких уравнений ax by c имеет хорошо известный

втеории чисел алгоритм для нахождения целочисленных решений.

Вавгусте 1900 г. в Париже состоялся II Международный конгресс математиков, на котором немецкий математик Д.Гильберт прочитал доклад «Математические проблемы». Среди 23 проблем, поставленных Гильбертом, десятая проблема может быть сформулирована в следующем виде.

Отыскать алгоритм для распознавания по произвольному диофантовому уравнению (12.1) — разрешимо ли это уравнение в целых числах.

Разумеется, в то время речь шла лишь о положительном решении проблемы — об «указании способа». То, что «способ решения» может отсутствовать — мысль о такой возможности в 1900 г. никому не приходила в голову. Лишь в 30-х гг. оформилось математически точное понятие алгоритма. К концу 40-х гг. вера в адекватность математически точного понятия алгоритма укоренилась уже настолько, что можно было серьезно ставить вопрос об отрицательном решении десятой проблемы Гильберта и других классических проблем, касающихся существования алгоритмов. В начале 50-х гг. появились работы, направленные на доказательство несуществования такого алгоритма.

В1970 г. российский математик Ю.В. Матиясевич завершил доказательство алгоритмической неразрешимости десятой проблемы Гильберта.

ТЕОРЕМА 12.2 (Ю.В.Матиясевич). Не существует алгоритма для распознавания по произвольному диофантовому уравнению, разрешимо ли это уравнение в целых числах.

120