Проблема самоприменимости

Объектом изучения в теории алгоритмов является, прежде всего, алгоритмическая разрешимость некоторой массовой задачи [19]. Разрешимая задача – для которой имеется абстрактная модель, за конечное число шагов проверяющая для любых входных данных, имеется ли решение данной задачи.

Напомним, что машина называется применимой к начальному слову, если она, начав работать с этим словом, придет в заключительное состояние.

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

Машина М₁, применимая к слову n(M₁), т.е. к коду своего собственного номера, называется самоприменимой. Предполагается, что машина Тьюринга универсальна, она читает код своего номера (программы), с ленты, расшифровывает его и в соответствии с ним выполняет необходимые действия в зависимости от начальной конфигурации (данных), также записанные на ленте. Машина, не применимая к слову n(M), называется несамоприменимой.

Проблема самоприменимости (впервые эта проблема рассмотрена отечественным математиком О.Б. Лупановым [24]) заключается в том чтобы по заданной программе Р для абстрактной машины узнать, применима ли она к своей собственной записи Р((Р)), где (Р) – запись программы или подпрограммы n(P) [7].

Например, программа машины, заменяющей символы 1 на 0, а 0 на 1, применима к любому слову, в частности и к своей записи, если мы закодируем записи программ в двоичном коде, что вполне возможно, поэтому она самоприменима, а программа В:

B: 1)?{l,2};

2) HLT,

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

Задача заключается в отыскании такого алгоритма, который определял бы для любой программы ее самоприменимость.

Теорема: Проблема самоприменимости алгоритмически неразрешима.

Доказательство проводится от противного [7]. Допустим, что такая программа S существует, то есть она применима к записи любой программы и перерабатывает записи несамоприменимых программ, например, в 0, а самоприменимых в 1.

Если Р несамоприменима, то S((P))=0.

Если Р самоприменима, то S((P))=1.

Но тогда возможна и программа R:

Если Р несамоприменима, то R((P))=0.

Если Р самоприменима, то R((P))= неопределено.

То есть R применима к записям несамоприменимых программ и неприменима к записям самоприменимых. Такую программу R можно построить путем композиции S◦B программ S и В, где В:

B: 1)?

2) HLT.

Здесь В применима к нулевым словам и неприменима к единичным (не останавливается в этом случае).

Но сама R либо самоприменима, либо несамоприменима.

Тогда:

Если R несамоприменима, то R((R))=0.

Если R самоприменима, то R((R))= неопределено.

Получается, что если R несамоприменима, то R((R))=0, то есть, определено, что означает, что R самоприменима. Если R самоприменима, то R((R))= неопределено, т.е. R несамоприменима.

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

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

Используя результат, доказанный теоремой, можно доказать неразрешимость других алгоритмических проблем. Укажем, например, проблему применимости к начальному слову. Она состоит в следующем: указать алгоритм, который по машине М и слову Х устанавливал бы, применима машина М к слову Х или нет.

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

Доказательство сводится к проблеме самоприменимости, которая неразрешима, как доказано выше.

Неразрешимости становятся бытом математики, и с их существованием приходится считаться [19]. С теоретической точки зрения, неразрешимость – не неудача, а научный факт. Знание основных неразрешимостей теории алгоритмов должно быть для специалиста по дискретной математике таким же элементом научной культуры, как для физика – знание о невозможности вечного двигателя. Если же важно иметь дело с разрешимой задачей (а для прикладных наук это стремление естественно), то следует четко представлять себе два обстоятельства. Во-первых (об этом уже говорилось при обсуждении проблемы остановки), отсутствие общего алгоритма, решающего данную проблему, не означает, что в каждом частном случае этой проблемы нельзя добиться успеха. Поэтому, если проблема неразрешима, надо искать ее разрешимые частные случаи. Во-вторых, появление неразрешимости – это, как правило, результат чрезмерной общности задачи (или языка, на котором описаны объекты задачи). Задача в более общей постановке имеет больше шансов оказаться неразрешимой.

Кроме понятий разрешимости и неразрешимости, вводится понятие сложности алгоритмов.

Дата добавления: 2015-07-11