В рамках ликбеза в уютной жежешечке: теорема Райса

Давайте рассмотрим все алгоритмы, существующие на свете, и попытаемся узнать, можно ли автоматически, с помощью машины (т.е. опять же алгоритма) отвечать на какие-то вопросы, касающиеся тех или иных алгоритмов.

Рассмотрим два алгоритма и . Назовем их эквивалентными, если на одном и том же входе они оба либо не останавливаются, либо выдают один и тот же ответ.

Любой алгоритм имеет текст. Текст алгоритма — строка в некотором ограниченном алфавите. Так что мы можем выписать все строки, которые существуют в этом алфавите (например, в лексикографическом порядке), этих строк счетное число, и можно пронумеровать их последовательно натуральными числами. Некоторые из этих строк представляют собой корректные алгоритмы, остальные же — "не компилирующиеся" — будем считать алгоритмами, которые всегда зацикливаются. Итак, каждый алгоритм получил свой уникальный номер.

Рассмотрим некоторое числовое множество . Назовем его инвариантным, если выполняется следующее свойство: номера любых двух эквивалентных алгоритмов либо оба лежат в , либо оба не лежат в нем.
Например, множество "Алгоритмы, которые на входе 1 выдают 39" — инвариантно. Аналогично инвариантными являются множества "Алгоритмы, которые останавливаются хоть на каком-нибудь входе", "Алгоритмы, которые возвращают только четные числа", "Алгоритмы, которые никогда не зацикливаются" и так далее.

Фактически, понятие инвариантного множества можно представлять как некоторое свойство алгоритма. Причем мы берем только свойства, характеризирующие алгоритм как класс — зависящие от его входа, выхода и факта конечного времени работы. Например, множество "Алгоритмы, выполняющие ровно 42 шага" — не инвариантно.

Очевидно, если множество — инвариантно, то его дополнение также инвариантно.

Множество называется разрешимым, если для него можно построить разрешающий алгоритм , который для любого числа на входе всегда останавливается и выдает 1, если , и 0, если .
Простой пример разрешимого множества — простые числа. Сюда же относятся четные числа, любые конечные множества, все множество , и еще многие различные примеры. Существуют также неразрешимые множества, но в данном посте этот вопрос затрагивать не стоит.

Множество называется перечислимым, если для него можно построить полуразрешающий алгоритм , который принимает на вход число , и возвращает 1, если , в противном же случае () — зацикливается.
Понятно, что любое разрешимое множество является перечислимым: разрешающий алгоритм легко превратить в полуразрешающий, добавив ему в конец вечный цикл вместо возвращения значения 0. Гораздо интереснее вопрос "Существует ли перечислимое неразрешимое множество?" Правильный ответ — да, существует, и не одно, однако построение конкретных примеров тоже выходит за рамки данного поста.

Теорема Райса (в некоторых редакциях теорема Успенского-Райса) утверждает поразительный факт:
Любое нетривиальное свойство алгоритма является неразрешимым.
Иными словами:
Если некоторое инвариантное множество разрешимо, то имеет место либо , либо .

( Доказательство )

Таким образом, принципиально невозможно построить такую среду/оболочку/систему/IDE, которая по коду данного ей произвольного алгоритма будет автоматически определять, справедливо ли для него какое-то специфическое свойство, каким бы простым и очевидным это свойство ни было. В частности, неразрешима так называемая проблема останова — не существует алгоритма, который по коду другого алгоритма и входному числу определил бы, остановится ли на входе .

Примечательно, что огромное количество программистов, в глаза не видевших никогда теорию алгоритмов и theoretical computer science, свято уверены, что любую задачу на свете можно решить и запрограммировать, были бы время и ресурсы.

Если бы.