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

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

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