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

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

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

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

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

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

Литература

  • В. И. Игошин. Математическая логика и теория алгоритмов. М.: Академия, 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.  (англ.)

См. также

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.