Т. А. Сливина математическая логика и теория алгоритмов

Теорема Чёрча. Проблема распознавания выводимости алгоритмически неразрешима.
2. Неразрешимость проблемы распознавания самоприменимости.
Введем предварительно понятие шифра машины Тьюринга. До сих пор мы записывали программу машины Тьюринга в виде двумерной таблицы т п. Однако ее можно изобразить в одномерном варианте, записывая последовательно пятерки символов так, что первый символ пятерки указывает столбец таблицы, второй – строчку таблицы, а последующие три – символы той тройки, которая располагается в таблице на пересечении указанных строки и столбца.
Так, например, вместо схемы, изображенной на рис. 7, будет получена одномерная строка:
a₀q₁a₀пq₃q₁нq₂q₁лq₁q₁лq₁a₀q₂a₀лq₄… (1)
Поступая аналогично, можно при рассмотрении конфигураций условиться о том, чтобы букву состояния писать не под обозреваемой буквой, а непосредственно левее ее. Например, ранее встречающуюся конфигурацию
     
q₄
будем записывать в виде     q₄  
Ясно, что каждую букву строки (1) можно переименовать. Сделаем это, соблюдая следующие условия:

1. 
   строка (1) должна однозначно разбиваться на отдельные кодовые группы;
   
2. 
   кодовые символы должны быть трех видов:
   

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

Алфавит	Буква	Кодовая группа	Примечания
Буквы адресов	л	101	Один нуль между 1
	н	1001	два нуля между 1
	п	10001	три нуля между 1
Внешний алфавит	а0	100001 4 нуля	четное число нулей, большее двух
	а1	10000001 6 нулей
	………	……………………..…..
	аn	10...01 2(n+2) нулей
Внутренний алфавит	q1	1000001 5 нулей	нечетное число нулей, большее трех
	q2	100000001 7 нулей
	……..	………………………….
	qm	10...01 2(n+1)+1 нулей

Если в строке (1) считать |, ,  соответственно буквами a₁, a₂, а₃, то при такой системе кодирования строка (1) запишется так:

100001100000110000110001100000000011000000110000011000000001…(2)

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

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

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