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

[skiminok]

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

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

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

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

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

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

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

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

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

Доказательство проведем методом от противного. Пусть существует разрешимое инвариантное множество , и оно нетривиально.

Рассмотрим алгоритм , который зацикливается на любом своем входе. Он либо принадлежит классу , либо его дополнению; пускай для определенности он лежит в классе .

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

Пусть — какое-нибудь перечислимое неразрешимое множество. Мы знаем, что такие в принципе существуют, а какое это конкретно множество, здесь неважно.

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

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

Теперь зафиксируем один из параметров функции , превратив её в функцию от одного аргумента с параметром , или . Её определение как алгоритма теперь можно переписать следующим образом:

Действительно, в одном случае она тождественно совпадает с алгоритмом , а в другом — с никогда не останавливающемся алгоритмом .

У , как у любого алгоритма, есть свой номер. Обозначим его .

Итак, если , то ведет себя так же, как и алгоритм , а стало быть, в этом случае они эквивалентны. По определению инвариантного множества тоже лежит в , как и число .

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

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

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

Если бы.

Comments

[mr-aleph.livejournal.com]

да, но для частных случаев алгоритмов алгоритмы вывода частных свойств построить можно =)

[skiminog.livejournal.com]

Безусловно) Но это уже темы для длительных марудных исследований в стиле "А если мы запретим в алгоритмах то-то и то-то, насколько ограничится класс языков, можно ли будет что-то сказать наверняка про свойства?" Я не видел ни одного примера такой статьи... но честно сказать, и не искал.

Ну и кроме того, существуют же и неинвариантные свойства.

[sofigenr.livejournal.com]

ты разрушил надежды несчастных искателей.)