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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Другая формулировка теоремы Райса[править | править вики-текст]

A\subsetЧРФ1, A\ne\empty, A\neЧРФ1, 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.