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

Говорят, что существует тьюрингов алгоритм решения класса задач Z, если существует такая машина Тьюринга Т с внешним алфавитом А, что:

1) для условия любой задачи существует слово u_z над А, кодирующее условие задачи z (дающее его запись на ленте машины);

2) машина Т применима к слову u_z;

3) v_z = T(u_z) является словом, кодирующим ответ задачи z.

Сама работа машины Т над словом u_z называется применением алгоритма, заданного машиной Т, к задаче z.

Класс задач Z, для которого существует решающий его тьюрингов алгоритм, называется алгоритмически разрешимой по Тьюрингу проблемой Z.

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

Возникает естественный вопрос: «Существуют ли алгоритмически неразрешимые по Тьюрингу проблемы?» Оказывается, есть. «Поставщиком» таких проблем является сама теория машин Тьюринга.

Универсальный алфавит; универсальная кодировка

Каждая машина Тьюринга имеет три алфавита: внешний А, внутренний Q и алфавит сдвигов S. Все три алфавита - конечные множества, и можно считать, что

.

Тогда любое слово над однозначно разбивается на слоги (подслова) (возможно, и однобуквенные) над алфавитами A, Q, S. В частности, любую клетку программы машины как отображения можно закодировать как пятибуквенное слово над , задающее соответствие . Если условиться, что программа выписывается последовательно по столбцам сверху вниз, то мы получим стандартную запись программы в виде «длинного» слова над алфавитом . Поставим следующий вопрос: «Нельзя ли выбрать достаточно простой алфавит, с помощью слов которого можно будет кодировать все буквы, а значит, и слова над (т.е. внешние слова и программу машины)?» Оказывается, в качестве такого простого алфавита, называемого универсальным, можно взять двухбуквенный алфавит {0; 1}. Опишем стандартную кодировку букв алфавита словами над
{0; 1} с помощью таблицы кодирования (см. табл. 15.6).

Кодировка с помощью этой таблицы называется стандартной. (Ясно, что стандартная кодировка допускает однозначное декодирование дли любых A, Q, S. Поэтому можно считать, что всегда применяется кодировка с помощью {0; 1} и что все машины работают со словами над алфавитом {0; 1}.

Таблица 15.6.

Буква	Код (слово) над {0; 1}
Сдвиги	-1
+1
Буквы	Λ
…	…
…	…
Состояния
…	…
…	…

Машина Тьюринга Т называется самоприменимой, если она применима к слову и_Т стандартной записи на ленте своей программы.

Это определение разбило все множество машин Тьюринга МТ на два класса: MT_S - класс самоприменимых и MT_пS - класс несамоприменимых машин.

Сформулируем проблему распознавания самоприменимости: «Существует ли такая машина Тьюринга S, которая умеет распознавать самоприменимость, т. е. по слову и_Т, кодирующему программу машины Т, сообщать, является ли машина Т самоприменимой или нет?» Оказывается, имеет место следующая теорема.

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

Допустим противное, т. е. что существует машина S, решающая проблему самоприменимости, причем

S (и_Т)= 1, если Т - самоприменима,

S (и_Т)= 0, если Т - несамоприменима.

Если машина S существует, то ее можно перестроить в машину , которая в случае, когда и_Т - кодировка программы несамоприменимой машины, перерабатывает и_Т в слово «0» и останавливается, а в случае, когда и_Т - кодировка программы самоприменимой машины, «вы­печатывает», уходя вправо, бесконечный хвост «1». Покажем, что существование машины , а значит и S, ведет к противоречиям. Для этого применим к слову . Возможны два исхода:

а) после применения к машина напечатает 0 и остановится, но, с одной стороны, это означает (0) - несамоприменимость, а с другой (остановка машины) - самоприменимость;

б) в результате применения к идет без остановки печать бесконечного хвоста единиц. Хвост единиц означает теперь самоприменимость, а это противоречит тому, что машина не останавливается.

Полученное противоречие и доказывает теорему.