Неразрешимые алгоритмические проблемы

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

На этот вопрос теория алгоритмов в ряде случаев дает отрицательный ответ. Один из первых результатов такого типа получен американским математиком Чёрчем в 1936 году. Он касается проблемы распознавания выводимости в математической логике.

1. Неразрешимость проблемы распознавания выводимости в математической логике.

Как известно, аксиоматический метод в математике заключается в том, что все предложения (теоремы) данной теории получаются посредством формально-логического вывода из нескольких предложений (аксиом), принимаемых в данной теории без доказательства.

В математической логике описывается специальный язык формул, позволяющий любое предложение математической теории записать в виде вполне определенной формулы, а процесс логического вывода из посылки А следствия Б может быть описан в виде процесса формальных преобразований исходной формулы. Это достигается путем использования логического исчисления, в котором указана система допустимых преобразований, изображающих элементарные акты логического умозаключения, из которых складывается любой, как угодно сложный формально-логический вывод.

Вопрос о логической выводимости предложения В из посылки А в избранном логическом исчислении является вопросом о существовании дедуктивной цепочки, ведущей от формулы А к формуле В.

В связи с этим возникает проблема распознавания выводимости: для любых двух формул А а В в логическом исчислении узнать, существует ли дедуктивная цепочка, ведущая от А к Б, или нет.

Решение этой проблемы понимается в смысле вопроса о существовании алгоритма, дающего ответ при любых А и Б. Результат Чёрча формулируется следующим образом:

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

2. Неразрешимость проблемы распознавания самоприменимости.

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

Поступая аналогично, можно при рассмотрении конфигурации условиться о том, чтобы букву Состояния писать не под обозреваемой буквой, а непосредственно левее ее.

Например, ранее встречающуюся конфигурацию

Q4 будем записывать в виде | q4|| • В связи с этим будем пользоваться следующей таблицей кодирования: Алфавит Буква Кодовая группа Примечания Буквы адресов л Один нуль между 1     н два нуля между 1     п три нуля между 1 Внешний алфавит а0 100001 4 нуля четное число нулей, большее двух     а1 10000001 6 нулей                                   an 10...01 2(n+2) нулей     Внутрен-ний алфавит q1 1000001 5 нулей нечетное число нулей, большее трех     q2 100000001 7 нулей         ..                   qm 10...01 2(n+1)+1 нулей     Подобную строчку из единиц и нулей, составленную для функциональной схемы или для отдельной конфигурации называют шифром функциональной схемы или широм конфигурации. Пусть теперь на ленте машины Тьюринга изображен ее же собственный шифр, записанный в алфавите машины. Возможны два случая: 1. Машина применима к своему шифру, т.е. она перерабатывает этот шифр и после конечного числа тактов останавливается. 2. Машина не применима к своему шифру, т.е. машина никогда не переходит в стоп-состояние. Таким образом, сами машины (их шифры) разбиваются на два класса: класс самоприменимых и класс несамоприменимых тьюринговых машин. Поэтому возникает следующая массовая проблема: проблема распозн ваемости самоприменимости. По любому заданному шифру установить, к какому классу относится машина, зашифрованная им: к классу самоприменимых или несамоприменимых? Теорема. Проблема распознавания самоприменимости алгоритмически не разрешима. Доказательство. Предположим противное. Пусть такая машина А существует. Тогда в А всякий самоприменимый шифр перерабатывается в какой-то символ s (имеющий смысл утвердительного ответа на поставленный вопрос о самоприменимости), а всякий несамоприменимый шифр - в другой символ tt (имеющий смысл отрицательного ответа на поставленный вопрос). В таком случае можно было построить и такую машину В, которая по-прежнему перерабатывает несамоприменимые шифры в s, в то время как к самоприменимым шифрам В уже не применима. Этого можно было добиться путем такого изменения схемы машины В, чтобы после появления символа а вместо появления стоп-состояния, машина начала бы неограниченно повторять этот же символ. Таким образом, В применима ко всякому несамоприменимому шифру (вырабатывается при этом символ t) и не применима к самоприменимым шифрам. Но это приводит к противоречию. Действительно: 1) пусть машина В самоприменима, тогда она применима к своему шифру В и перерабатывает его в символ t; но появление этого символа как раз и должно означать, что В несамоприменима; 2) пусть В несамоприменима, тогда она не применима к В, что должно означать как раз, что В самоприменима. Полученное противоречие доказывает теорему.