Разрешимость в теории алгоритмов.

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

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

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

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

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

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

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

B: 1) ?{l,2};

2) HLT,

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

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