Не распознаваемость самоприменимости машины Тьюринга

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

Для этого нам понадобятся следующие теоремы и определения.

Теорема 3.2.1. (о композиции машин Тьюринга). Каковы бы ни были машины Тьюринга Т₁ и Т₂ в алфавите А, можно построить работающую в том же алфавите такую машину Т, что для всех слов a над алфавитом А будет выполнено равенство Т(a)=Т₂(Т₁(a)).

Доказательство этой теоремы осуществляется просто. Внутренние состояния машин Т₁ и Т₂ (включая начальные состояния) переименовываются, причем в функциональной схеме машины Т₁ переход в заключительное состояние заменяется переходом в начальное состояние машины Т₂. При этом функциональные схемы объединяются в одну.

Теорема 3.2.2. (о двоичном моделировании машины Тьюринга) Какова бы ни была машина Т₁ в алфавите А, может быть построена такая машина Т в алфавите В={a₀, 0, 1}, что для любых слов a₁, a₂ над алфавитом А и их кодов b₁, b₂ над алфавитом В Т(b₁)= Т(b₂) тогда и только тогда, когда Т₁(a₁)= a₂.

Из этой теоремы следует, что в теории машин Тьюринга вполне можно рассматривать только те машины, которые работают в двоичном алфавите. Более того, кроме двух способов задания машины Тьюринга (в виде функциональной схемы и списка команд) возможен третий способ ее записи – в виде двоичного слова.

При этом с помощью побуквенного обратимого (конструктивного) двоичного кодирования кодируются в общем случае:

– символы внешнего алфавита и алфавита внутренних состояний,

– символы, используемые при записи команд машины Тьюринга (Л, П, →,«оставаться на месте»),

– символ, фиксирующий начало и конец программы,

– символ, служащий разделителем между командами.

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

Заметим также, что двоичная запись машины Тьюринга однозначно определяет натуральное число. Натуральные числа, являющиеся записями машины Тьюринга называют геделевскими – по имени австрийского математика Курта Геделя, впервые в 30 годы XX века использовавшего номера объектов вместо них самих для формальных рассуждений об этих объектах.

К.Гедель

Рассматривая далее множество машин Тьюринга {T} будем считать, что каждая из них задана своей двоичной записью ŒТŒ. Широко известная в теории алгоритмов массовая проблема остановки в этих терминах формулируется следующим образом.

Применима ли машина Тьюринга Т, заданная своей записью ŒТŒ, к двоичному слову p или нет?

Еще одна известная массовая проблема теории алгоритмов – проблема самоприменимости – звучит так.

Применима ли машина Тьюринга Т, заданная своей записью ŒТŒ, к своей записи ŒТŒ или нет?

Очевидно, что проблема самоприменимости является частным случаем проблемы остановки. И если проблема самоприменимости алгоритмически неразрешима, то и проблема остановки относится к числу алгоритмически неразрешимых проблем.

Тот факт, что проблема самоприменимости алгоритмически неразрешима, фиксирует следующая теорема.

Теорема 3.2.3. (о нераспознаваемости самоприменимости). Не существует машины Тьюринга S, которая по записи ŒТŒ определяла бы, самоприменима машина Т или нет.

Доказательство. Предположим противное и допустим, что существует машина Тьюринга S, распознающая самоприменимость. Без ограничения общности можно считать, что S(ŒCŒ)=1, а S(ŒНŒ)=0, где ŒCŒ – произвольная самоприменимая машина Тьюринга, а ŒНŒ – произвольная несамоприменимая машина Тьюринга.

Введем в рассмотрение машину Т₁ с алфавитом внутренних состояний Q={q₀, q₁, q₂ }, работающую в алфавите A={a₀, 0, 1} в соответствие со следующей функциональной схемой.

Как видно из приведенной схемы, если первая буква исходного слова a есть 0, то Т₁(a)=a. Если же исходное слово a пусто или начинается с 1, то Т₁ неприменима к слову a, Т₁(a)=1111…

Определим теперь новую машину Тьюринга S₁ как композицию машины S и машины Т₁, полагая S₁(a)=Т₁(S(a)).

Предположим далее, что машина S₁ самоприменима. Это означает, что ŒS₁Œ – запись самоприменимой машины и по определению машины S S(ŒS₁Œ)=1. В то же время,

S₁(ŒS₁Œ)=Т₁(S(ŒS₁Œ))=Т₁(1)=111….,

что означает несамоприменимость машины S₁. Противоречие налицо.

Предположение о том, что машина S₁ несамоприменима, влечет за собой (по определению машины S) соотношение S(ŒS₁Œ)=0. Но по определению машины S₁ S₁(ŒS₁Œ)=Т₁(S(ŒS₁Œ))=Т₁(0)=0, что означает самоприменимость машины S₁.

Вновь получаем противоречие.

Иными словами, предположение о существовании машины S, распознающей самоприменимость приводит к противоречию.

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

Следствие. Проблема остановки алгоритмически неразрешима.

Проблема самоприменимости в теории алгоритмов явилась первой алгоритмически неразрешимой проблемой, от которой отталкивались в дальнейших исследованиях.