Самоприменимость
Самопримени́мость в теории алгоритмов — свойство алгоритма успешно завершаться на данных, представляющих собой формальную запись этого же алгоритма.
Задача распознавания самоприменимости является алгоритмически неразрешимой и сводится к тому, чтобы найти алгоритм, позволяющий за конечное число шагов по формальной записи некоего алгоритма узнать, является ли он самоприменимым или нет. Хотя эта задача несколько искусственна и не представляет самостоятельного интереса, но часто используется для того, чтобы доказать неразрешимость других, более сложных задач. Общий метод для подобных выводов состоит в том, что из предположения о существовании алгоритма, решающего некую задачу, выводится существование алгоритма, решающего задачу распознавания самоприменимости.
Доказательство алгоритмической неразрешимости
Доказательство от противного. Допустим, что алгоритм, распознающий самоприменимость, существует. На основании тезиса Тьюринга существует и машина Тьюринга, реализующая этот алгоритм. Обозначим такую машину как [math]\displaystyle{ A }[/math]. На её ленту заносится каким-либо образом закодированная программа другой машины Тьюринга, а после работы занесённые данные перерабатываются в какое-то слово [math]\displaystyle{ y }[/math], если исходная программа была самоприменима, или в слово [math]\displaystyle{ n }[/math], если она была несамоприменима.
Вторым шагом немного модифицируем машину [math]\displaystyle{ A }[/math] так, чтобы она по-прежнему перерабатывала несамоприменимые программы в [math]\displaystyle{ n }[/math], а на самоприменимых программах зацикливалась, то есть являлась неприменимой к ним. Сделать подобное преобразование очень легко — после записи слова [math]\displaystyle{ y }[/math] машина не заканчивает работу, а продолжает бесконечно записывать его на ленту. Обозначим эту машину как [math]\displaystyle{ A_1 }[/math]. Существование такой машины приводит к противоречию, потому что [math]\displaystyle{ A_1 }[/math] не может быть ни самоприменимой, ни несамоприменимой. Действительно, если [math]\displaystyle{ A_1 }[/math] самоприменима, то она применима к собственной записи. Но по построению машины [math]\displaystyle{ A_1 }[/math] это свидетельствует как раз о том, что [math]\displaystyle{ A_1 }[/math] несамоприменима. Если же [math]\displaystyle{ A_1 }[/math] несамоприменима, то по построению она применима к собственной записи, так как она применима к любой записи несамоприменимой машины. Но это как раз означает, что [math]\displaystyle{ A_1 }[/math] самоприменима. Исходя из этого делается вывод о невозможности построения машины [math]\displaystyle{ A }[/math], поскольку тогда из неё легко можно было бы получить [math]\displaystyle{ A_1 }[/math].
Литература
- В. И. Игошин. Математическая логика и теория алгоритмов. — М.: Академия, 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. (англ.)