WikiSort.ru - Не сортированное

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

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

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

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

Вторым шагом немного модифицируем машину ${\displaystyle A}$ так, чтобы она по-прежнему перерабатывала несамоприменимые программы в ${\displaystyle n}$ , а на самоприменимых программах зацикливалась, то есть являлась неприменимой к ним. Сделать подобное преобразование очень легко — после записи слова ${\displaystyle y}$ машина не заканчивает работу, а продолжает бесконечно записывать его на ленту. Обозначим эту машину как ${\displaystyle A_{1}}$ . Существование такой машины приводит к противоречию, потому что ${\displaystyle A_{1}}$ не может быть ни самоприменимой, ни несамоприменимой. Действительно, если ${\displaystyle A_{1}}$ самоприменима, то она применима к собственной записи. Но по построению машины ${\displaystyle A_{1}}$ это свидетельствует как раз о том, что ${\displaystyle A_{1}}$ несамоприменима. Если же ${\displaystyle A_{1}}$ несамоприменима, то по построению она применима к собственной записи, так как она применима к любой записи несамоприменимой машины. Но это как раз означает, что ${\displaystyle A_{1}}$ самоприменима. Исходя из этого делается вывод о невозможности построения машины ${\displaystyle A}$ , поскольку тогда из неё легко можно было бы получить ${\displaystyle 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.  (англ.)

См. также

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