Теорема Райса

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

Теорема названа в честь американского математика Генри Гордона Райса, доказавшего её в 1951 году в своей докторской диссертации^[1]. Её следует отличать от теоремы Райса-Шапиро, названной в честь Райса и Нормана Шапиро.

Другая формулировка теоремы Райса

$A\subset$ЧРФ¹, $A\ne\empty$, $A\ne$ЧРФ¹, $B=\{n: \theta(n)\in A\}$, тогда $\chi_B\,\!$ не является ЧРФ.

Здесь $\chi_B\,\!$ - характеристическая функция множества $B\,\!$.

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

Под вызовом программы x, на вход которой подана программа y, мы будем подразумевать вызов программы x, на вход которой подан номер программы y в лексикографическом порядке.

Пускай множество всех программ $P$ разбито на два непустых класса, $A$ и $B$, $A\cup B=P$, $A\cap B=\empty$, причём функционально тождественные (вычисляющие одну и ту же функцию) программы относятся к одному и тому же классу. Докажем, что задача распознавания, к какому из классов принадлежит программа, алгоритмически неразрешима.

Доказываем от противного. Пускай распознающая программа есть. Обозначим её $p_0$. Обозначим через $p_1$ программу, которая не останавливается ни при каком входе. Пускай она принадлежит к классу $A$. По условию, класс B непуст, выберем из него любую программу и обозначим её $p_2$.

Для любой программы $p$ определим программу $p'$, которая, получив на вход $x$, делает следующее:

1. вычисляет $p(p)$
2. отбросив результат предыдущего шага, вычисляет $p_2(x)$ .

Определим, к какому классу относится $p'$.

• Если $p(p)$ не останавливается, то $p'$ зациклится на первом шаге, следовательно, $p'$ функционально тождественна $p_1$, следовательно, относится к классу $A$.
• Если $p(p)$ останавливается, то первый шаг на окончательный результат не влияет, следовательно $p'$ функционально тождественна $p_2$, следовательно, относится к классу $B$.

Теперь рассмотрим программу $p_3$. Получив на вход любую программу $p$, она делает следующее:

1. Строит $p'$
2. Вычисляет $p_0(p')$

Эта программа распознаёт, останавливается p(p) или нет.

Рассмотрим, наконец, программу $p_4$. Получив на вход любую программу $p$, она делает следующее:

1. Вычисляет $p_3(p)$
2. Если оказалось, что $p(p)$ не останавливается, $p_4$ немедленно останавливается
3. Иначе вызывает бесконечный цикл

Таким образом, для любой программы p, $p_4(p)$ останавливается тогда и только тогда, когда $p(p)$ не останавливается. Подставляя $p=p_4$, получаем, что $p_4(p_4)$ останавливается тогда и только тогда, когда $p_4(p_4)$ не останавливается. Противоречие.

Примечания

1. ↑ Rice, H. G. (March 1953). «Classes of Recursively Enumerable Sets and Their Decision Problems». Transactions of the American Mathematical Society 74 (2): 358. DOI:10.2307/1990888. Проверено 2011-09-29.