Математическая логика и теория алгоритмов
|
2.4 Алгоритмически неразрешимые задачи |
назад | оглавление | вперёд |
       Согласно Тьюрингу алгоритм решения задачи – это машина Тьюринга для вычисления подходящей арифметической функции. Если машина Тьюринга существует для решения задачи, то такая задача называется алгоритмически разрешимой, в противном случае задача алгоритмически неразрешима. В этом разделе будет показано существование алгоритмически неразрешимых задач, т.е. таких задач для которых не существует машины Тьюринга.
       Предварительно пронумеруем все машины Тьюринга следующим образом. Зафиксируем счетные множества символов и
. Будем считать, что внешние алфавиты всех МТ берутся из множества , при этом символ принадлежит всем внешним алфавитам МТ и интерпретируется как пустой символ. Символы внутренних алфавитов всех МТ берутся из множества A, а символы a0 и q0 принадлежат внутренним алфавитам всех МТ и интерпретируются как начальное и заключительное состояния соответственно.
       Каждому символу x из множества поставим в соответствие двоичную последовательность n(x) по следующему правилу:
x | n(x) |
R | 10 |
L | 100 |
H | 1000 |
a0 | 10000 |
a1 | 1000000 |
... | ... |
ai | 102i+4 |
... | ... |
q0 | 100000 |
q1 | 10000000 |
... | ... |
qj | 102j+5 |
... | ... |
       Пусть теперь внешний алфавит некоторой машины Тьюринга содержит символы множества {a0,0,1}. На ленте записан шифр этой машины, головка МТ обозревает самую левую единицу шифра, а машина находится в начальном состоянии q1. Машина T называется самоприменимой, если после начала работы в указанной конфигурации она через конечное число шагов попадет в заключительное состояние q0, в противном случае машина T называется несамоприменимой.
Пример 2.Машина является самоприменимой, поскольку после выполнения одной команды машина попадает в заключительное состояние независимо от того, что было записано на ленте (т.е. в том числе и если был записан шифр этой машины).
Пример 3.Программа машины не содержит состояния q0, поэтому машина не может попасть в это состояние и, следовательно, является несамоприменимой.
       Рассмотрим такую задачу: по шифру заданной машины Тьюринга требуется определить, является ли машина с этим шифром самоприменимой. Поскольку каждый алгоритм теперь отождествляется с подходящей МТ, то указанную задачу можно сформулировать более формально.
       Проблема самоприменимости. Пусть арифметическая функция p(x) определена следующим образом:
       
       Существует ли машина Тьюринга T в алфавите {a0,0,1}, которая правильно вычисляет функцию p(x)?
       Будем считать, что машина будет оставлять на ленте одну единицу в случае, если слово на ленте в начальной конфигурации было шифром некоторой самоприменимой машины, и будет оставлять 0, если слово на ленте в начальной конфигурации было шифром некоторой несамоприменимой машины.
Теорема. Проблема самоприменимости алгоритмически неразрешима.
Доказательство. Предположим противное, т.е. что существует машина Тьюринга T, которая решает проблему самоприменимости. Пусть {q0,q1,qm} - внутренний алфавит машины Т. Изменим программу машины Т следующим образом. В командах, содержащих символ q0, заменим q0 на qm+1. Добавим к программе команды . В результате получим новую машину Тьюринга, которую обозначим через T1.
       Предположим, что в начальный момент на лентах машин T и T1 был записан шифр какой-то самоприменимой машины Тьюринга и обе машины начинают работу. Действия машин будут идентичны до тех пор, пока машина T не попадет в состояние q0, записав на ленте 1 и остановит головку над ячейкой с этой единицей. Машина T1 также напечатает на ленте единицу и поместит головку над этой ячейкой, но не остановится, перейдет в состояние qm+1 и продолжит работу, выполняя новые команды. В состояние q0 машина T1 попасть не может.
       Если в начальный момент на лентах машин T и T1 был записан шифр некоторой несамоприменимой машины Тьюринга, то каждая из них попадет в заключительное состояние, выдав в качестве результата 0.
       Очевидно, что каждая из машин Тьюринга в алфавите {a0,0,1} является либо самоприменимой, либо несамоприменимой. Определим к какому классу относится машина T1. Для этого на ленте запишем шифр этой машины и запустим её. Если машина T1 самоприменимая, то ее шифр является шифром самоприменимой машины, и машина будет действовать так, как описано выше, т.е. машина никогда не попадет в заключительное состояние и, следовательно, самоприменимой быть не может.
       Предположим, что машина T1 несамоприменимая и ее шифр является шифром несамоприменимой машины, поэтому через конечное число шагов машина попадет в состояние q0. Это означает, что машина T1 самоприменимая, что противоречит предположению.
       Теорема доказана.
       Приведем еще один пример неразрешимой проблемы, которая называется проблема останова. Проблема останова заключается в том, чтобы по любой машине T и любой последовательности Sв ее внешнем алфавите узнать применима ли машина T к последовательности S, т.е. остановится ли машина T через конечное число шагов после начала работы с начальной последовательностью S на ленте. Данная проблема алгоритмически неразрешима, т.к. если бы она была разрешимой, то взяв в качестве S шифр машины T, получили бы разрешимость проблемы самоприменимости. Таким образом, проблема останова сводится к проблеме самоприменимости.