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

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

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

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

$A\subset$ЧРФ¹, $A\neq \emptyset$, $A\neq$ЧРФ¹, $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=\emptyset$, причём функционально тождественные (вычисляющие одну и ту же функцию) программы относятся к одному и тому же классу. Докажем, что задача распознавания, к какому из классов принадлежит программа, алгоритмически неразрешима.

Доказываем от противного. Пускай распознающая программа есть. Обозначим её $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})$ не останавливается. Противоречие.