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

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

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

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

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

ЧРФ1, , ЧРФ1, , тогда не является ЧРФ.

Здесь - характеристическая функция множества .

Доказательство[править | править вики-текст]

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

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

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

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

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

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

  • Если не останавливается, то зациклится на первом шаге, следовательно, функционально тождественна , следовательно, относится к классу .
  • Если останавливается, то первый шаг на окончательный результат не влияет, следовательно функционально тождественна , следовательно, относится к классу .

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

  1. Строит
  2. Вычисляет

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

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

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

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

Примечания[править | править вики-текст]

  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.

Литература[править | править вики-текст]