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

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

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

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

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

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

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

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

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

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

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

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

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

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

К.Гедель

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

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

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

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

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

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

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

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

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

Q A	q1	q2
a0	q11Л	q21Л
0	q00	q21Л
1	q21Л	q21Л

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

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

Предположим далее, что машина 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, распознающей самоприменимость приводит к противоречию.

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

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

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

Лекция № 4. Рекурсивные функции

1. Примитивно-рекурсивные функции

2. Частично-рекурсивные и общерекурсивные функции