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