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

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

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

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

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

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

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

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

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

Так, например, вместо схемы, изображенной на рис. 7, будет получена одномерная строка:

а ₀ q ₁ а ₀ п q ₃ | q ₁ a н q ₂ a q ₁ a  q ₁  q ₁   q ₁ а ₀ q ₂ а ₀  q _4…..

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

Q4 будем записывать в виде | q4||. Ясно, что каждую букву строки (1) можно переиме­новать. Сделаем это, соблюдая следующие условия: 1. строка (1) должна однозначно разбиваться на от­ дельные кодовые группы; 2. кодовые символы должны быть трех видов: а) для букв, п, н; б) для букв внешнего алфавита; в) для букв, изображающих состояния машины. В связи с этим будем пользоваться следующей таб­лицей кодирования: Алфавит Буква Кодовая группа Примечания Буквы адресов  Один нуль между 1 н два нуля между 1 п три нуля между 1 Внешний алфавит а0 100001 4 нуля четное число нулей, a1 10000001 6 нулей большее двух ••• •••••••••   ап 10...01 2(n+2) нулей   Внутрен- ний ал- фавит q1 1000001 5 нулей нечетное число ну- лей, большее трех q2 100000001 7 нулей .……………… qт 10...01 2(n+1)+1 нулей Если в строке (1) считать|, a,   соответственно буквамиa1 a2, a3, то при такой системе кодирования строка (1) запишется так:

100001100000110000110001100000000011000000110000011000000001… (2)

Подобную строчку из единиц и нулей, составленную для функциональной схемы или для отдельной конфигура­ции называют шифром функциональной схемы или шиф­ром конфигурации.

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

1.Машина применима к своему шифру, т.е. она
перерабатывает этот шифр и после конечного числа так­
тов останавливается.

2. Машина не применима к своему шифру, т.е. ма­
шина никогда не переходит в стоп-состояние.

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

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

Доказательство. Предположим противное. Пусть такая машина А существует. Тогда в А всякий самопри­менимый шифр перерабатывается в какой-то символ  (имеющий смысл утвердительного ответа на поставленный вопрос о самоприменимости), а всякий несамопри-меннмый шифр - в другой символ т (имеющий смысл отрицательного ответа на поставленный вопрос). В та­ком случае можно было построить и такую машину. В, которая по-прежнему перерабатывает несамоприменимые шифры в , в то время как к самоприменимым шифрам В уже не применима. Этого можно было добиться путем такого изменения схемы машины В, чтобы после появле­ния символа  вместо появления стоп-состояния, машина начала бы неограниченно повторять этот же символ.

Таким образом, В применима ко всякому несамоприменимому шифру (вырабатывается при этом символ т) и не применима к самоприменимым шифрам. Но это приво­дит к противоречию. Действительно:

1) пусть машина В самоприменима, тогда она приме­нима к своему шифру В и перерабатывает его в символ , но появление этого символа как раз и должно озна­чать, что В несамоприменима;

2) пусть В несамоприменима, тогда она не примени­ма к B, что должно означать как раз, что В самоприменима. Полученное противоречие доказывает теорему.