Математическая логика и теория алгоритмов

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
... ...
       Очевидно, что последовательности n(x1) и n(x2) могут совпадать только тогда, когда x1=x2.
       Команде МТ при сопоставим последовательность такого вида (числа здесь не перемножаются, а последовательно записаны).
       
       Все команды МТ упорядочим в соответствие с лексикографическим порядком левых частей команд и МТ сопоставим набор нулей и единиц, состоящий из последовательно записанных двоичных наборов для каждой команды МТ. Эту последовательность назовем шифром машины Тьюринга.
       Разные машины Тьюринга имеют различные шифры, при этом по шифру можно однозначно восстановить программу машины Тьюринга. Шифр машины состоит из нулей и единиц и всегда начинается с единицы. Его можно считать двоичной записью некоторого натурального числа.

Пример 1.Найдем шифр машины Тьюринга, вычисляющую функцию O(x)=0.
       При условии,что а0=0, a1=1,
       Программа вычислений выглядит так:
q11 → 0Rq2q20 → 1Hq0q21 → 0Rq2
       и машина имеет такой шифр:
       

       Пусть теперь внешний алфавит некоторой машины Тьюринга содержит символы множества {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, получили бы разрешимость проблемы самоприменимости. Таким образом, проблема останова сводится к проблеме самоприменимости.


назад | оглавление | вперёд