Самоприменимость

Самопримени́мость в теории алгоритмов — свойство алгоритма успешно завершаться на данных, представляющих собой формальную запись этого же алгоритма.

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

Доказательство алгоритмической неразрешимости

Доказательство от противного. Допустим, что алгоритм, распознающий самоприменимость, существует. На основании тезиса Тьюринга существует и машина Тьюринга, реализующая этот алгоритм. Обозначим такую машину как $A$. На её ленту заносится каким-либо образом закодированная программа другой машины Тьюринга, а после работы занесённые данные перерабатываются в какое-то слово $y$, если исходная программа была самоприменима, или в слово $n$, если она была несамоприменима.

Вторым шагом немного модифицируем машину $A$ так, чтобы она по-прежнему перерабатывала несамоприменимые программы в $n$, а на самоприменимых программах зацикливалась, то есть являлась неприменимой к ним. Сделать подобное преобразование очень легко — после записи слова $y$ машина не заканчивает работу, а продолжает бесконечно записывать его на ленту. Обозначим эту машину как $A_1$. Существование такой машины приводит к противоречию, потому что $A_1$ не может быть ни самоприменимой, ни несамоприменимой. Действительно, если $A_1$ самоприменима, то она применима к собственной записи. Но по построению машины $A_1$ это свидетельствует как раз о том, что $A_1$ несамоприменима. Если же $A_1$ несамоприменима, то по построению она применима к собственной записи, так как она применима к любой записи несамоприменимой машины. Но это как раз означает, что $A_1$ самоприменима. Исходя из этого делается вывод о невозможности построения машины $A$, поскольку тогда из неё легко можно было бы получить $A_1$.

Литература

• В. И. Игошин Математическая логика и теория алгоритмов. — М.: Академия, 2004. — С. 369—370. — 448 с. — 5100 экз. — ISBN 5-7695-1363-2
• А. Л. Семёнов Самоприменимые программы // Математика текстов. — 2002. — 16 с. — 3000 экз. — ISBN 5-94057-006-2
• Е. М. Иванов Геделевский аргумент // К проблеме «вычислимости» функции сознания.
• Michiel Hazewinkel Undecidability // Encyclopaedia of Mathematics. — Berlin: Springer Netherland, 2002. — ISBN 1-4020-0609-8  (англ.)
• Arto Salomaa 4.3 Recursion Theorem and Basic Undecidability Results // Computation and automata. — Cambridge University Press, 1985. — Т. 25. — С. 90. — 284 с. — ISBN 9780521302456  (англ.)

См. также

• Проблема остановки