Теперь представим коды команд с помощью алфавита {1, }:

13 110 13 110 12 13 18 15 110 14 15 110 15 110 14 15 18 1 18 12,

где 1k есть единица, повторенная k раз.

3.2. Алгоритмически неразрешимые проблемы

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

моприменимой.

Возникает вопрос: существует ли машина MS , которая по коду любой машины M определяет, самоприменима ли она?

Если она существует, она должна быть применима к коду любой машины M и должна останавливаться на клетке с 1 в случае самоприменимости M , и на клетке с 0 в противном слу-

чае. Ответ на поставленный вопрос дает следующая теорема.

Теорема. MS не существует, то есть проблема самоприменимости алгоритмически неразрешима.

Доказательство. Пусть машина Тьюринга S решает проблему самоприменимости, т. е., начав работу с кода машины T , приходит в состояние

q01	,	(*)
если машина T самоприменима, и в состояние
q00	,	(**)
если T несамоприменима.

70