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

Проблему самоприменимости можно сформулировать весьма общим способом. Поскольку множество алгоритмов счётно, их можно занумеровать. Фиксируем некоторую нумерацию алгоритмов А$, А,… (повторения допустимы).

Кроме того, множество входов алгоритмов также счётно. Поэтому без ограничения общности считаем, что на вход алгоритму подаётся натуральное число.

Проблема самоприменимости. Пусть функция F: N —" N определена следующими правилами: F (i) = 1, если алгоритм А{ останавливается на входе г, и F (i) = 0 в противном случае.

Проблема самоприменимости состоит в вычислении функции F.

Теорема 4.18. Для. любой нумерации алгоритмов проблема самоприменимости алгоритмически неразрешима, т. е. функция F не является вычислимой.

Доказательство. Составим бесконечную табл ищу, в которой элемент S{j, стоящий в г-й строке и j-м столбце, равен 1, если алгоритм Ai останавливается на входе j, и равен 0 в противном случае. Заметим, что F (i) = вц.

Предположим, что существует алгоритм, который вычисляет F. Ясно, что тогда существует и такой алгоритм А, который на входе г вычисляет F (i), после чего останавливается, если F (i) = 0, а если F (i) = 1, то алгоритм «зацикливается» (т. е. продолжает работу бесконечно долго).

У алгоритма А есть номер в нумерации алгоритмов. Пусть этот помер равен N. Чему равно 5дгдг? Предположим, что Snn — F (N) — 1* Тогда с одной стороны это означает, что алгоритм А на входе с номером N останавливается (Snn = 1)? а с другой — что не останавливается (так как F (N) = 1). Если же Snn = Fn = 0, то получаем, что алгоритм не останавливается на входе N, так как Snn = О, но поскольку Fjv = 0, то из описания алгоритма А следует, что он останавливается. Итак, для любого из возможных значений 5. удг мы пришли к противоречию. Отсюда следует, что ложно предположение о существовании алгоритма, вычисляющего F. ?

Замечание 4.19. Применённый в этом доказательстве приём называется диагональной конструкцией. Впервые он был использован Г. Кантором для доказательства несчётности множества действительных чисел.

Замечание 4.20. Обратите внимание, что нумерация алгоритмов в проблеме самоприменимости произвольна и даже необязательно вы числима.

Замечание 4.21. В приведённом доказательстве есть фраза, начинающаяся словами «Ясно, что…». Большинство ошибок в математических рассуждениях скрываются именно за этим вводным оборотом и его синонимами.

Впрочем, в данном случае никакой ошибки нет. Однако уточнение рассуждения требует использования какого-нибудь формального определения алгоритма, например, машин Тыоринга.

Описанный в рассуждении алгоритм можно получить соединением машины, вычисляющей функцию F, и машины со следующим свойством: начиная работу на ленте, содержащей результат вычисления функции F, машина останавливается, если количество единиц на лейте равно 1, в противном случае она перемещает головку вправо бесконечно долго. Обратите внимание, что одна единица является кодом числа 0 в определении вычислимой функции на с. 165. Для корректности работы соединения машин нужно также потребовать, чтобы вторая машина выполняла указанные действия, начиная работу с любого места ленты.

Задача 4.4. Постройте машину Тьюринга, обладающую описанными в предыдущем замечании свойствами.

Проблему самоприменимости можно обобщить.

Проблема остановки. Она состоит в вычислении значения функции /s: N х N —> N, заданной правилами: fs (i, j) = = 1, если алгоритм А{ останавливается на входе.;, и fs (ij) = = 0 в противном случае.

Теорема 4.22. Проблема остановки при любой нумерации алгоритмов является алгоритмически неразрешимой.

Эта теорема легко следует из теоремы 4.18, поскольку.

Поэтому из вычислимости функции /s следует вычислимость функции самоприменимости F.

Мы сформулировали проблемы самоприменимости и остановки как задачи вычисления целочисленной функции от неотрицательных целочисленных аргументов. Есть другая формулировка этих задач, в которой нужно ответить на вопрос об остановке, если задано описание машины Тьюринга и входного слова. При такой формулировке удобно использовать введённое выше понятие разрешимого языка.

Определение 4.23. Обозначим через stop язык в алфавите {0,1}*, состоящий из тех описаний (M, w) машины Тьюринга М и её входного слова w, для которых М останавливается на входе ги.

Теорема 4.24. Язык stop неразрешти.

Доказательство этой теоремы следует из теоремы 4.22, поскольку с любым способом описания МТ и их входов можно связать нумерацию. Например, слова можно нумеровать в лексикографическом порядке.

Лексикографический порядок на словах в алфавите {0,1,…, га} определяется следующим правилом: слово и предшествует слову v в лексикографическом порядке (обозначение и -< v) тогда и только тогда, когда-либо длина и меньше чем длина г>, либо и = pasi, v = pbs2, где p, s, S2 € {0,1,…, n}*, a, b € {0,1,…, га} и a < b.

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

Задача 4.5. Постройте машины Тьюринга, которые.

• (а) но слову w строит следующее в лексикографическом порядке слово;
• (б) но слову w определяет его номер при нумерации в лексикографическом порядке.

Используя машины из задачи 4.5, можно вывести теорему 4.24 из теоремы 4.22 с помощью стандартного приёма, называемого сводимостью.

Предположим, что существует решающий алгоритм R для языка stop. Тогда функция /$ вычисляется следующим алгоритмом: по входу (i, j) он строит описание (Mj, Р), где — МТ, описание которой имеет номер i в лексикографическом порядке^[1]), после чего применяет алгоритм R к этому описанию и выдаёт значение 1, если (М*, Р) € stop, или 0 в противном случае.

Поскольку не существует алгоритма вычисления /s, то язык stop неразрешим.

• [1] В этом месте имеется ещё одно формальное затруднение — не всеслова являются описаниями МТ в смысле определения на с. 162. Преодолеть эту трудность можно сопоставлением таким словам некоторойфиксированной МТ А/о.