- Теорема Райса
-
В теории алгоритмов, теорема Райса гласит, что для любого нетривиального свойства вычислимых функций, определение, вычисляет ли произвольный алгоритм функцию с таким свойством, является алгоритмически неразрешимой задачей. Здесь свойство называется нетривиальным, если существуют и вычислимые функции, обладающие этим свойством, и вычислимые функции, не обладающие им.
Теорема названа в честь американского математика Генри Гордона Райса, доказавшего её в 1951 году в своей докторской диссертации[1]. Её следует отличать от теоремы Райса-Шапиро, названной в честь Райса и Нормана Шапиро.
Другая формулировка теоремы Райса
ЧРФ1,
,
ЧРФ1,
, тогда
не является ЧРФ.
Здесь
- характеристическая функция множества
.
Доказательство
Под вызовом программы x, на вход которой подана программа y, мы будем подразумевать вызов программы x, на вход которой подан номер программы y в лексикографическом порядке.
Пускай множество всех программ
разбито на два непустых класса,
и
,
,
, причём функционально тождественные (вычисляющие одну и ту же функцию) программы относятся к одному и тому же классу. Докажем, что задача распознавания, к какому из классов принадлежит программа, алгоритмически неразрешима.
Доказываем от противного. Пускай распознающая программа есть. Обозначим её
. Обозначим через
программу, которая не останавливается ни при каком входе. Пускай она принадлежит к классу
. По условию, класс B непуст, выберем из него любую программу и обозначим её
.
Для любой программы
определим программу
, которая, получив на вход
, делает следующее:
- вычисляет
- отбросив результат предыдущего шага, вычисляет
.
Определим, к какому классу относится
.
- Если
не останавливается, то
зациклится на первом шаге, следовательно,
функционально тождественна
, следовательно, относится к классу
.
- Если
останавливается, то первый шаг на окончательный результат не влияет, следовательно
функционально тождественна
, следовательно, относится к классу
.
Теперь рассмотрим программу
. Получив на вход любую программу
, она делает следующее:
- Строит
- Вычисляет
Эта программа распознаёт, останавливается p(p) или нет.
Рассмотрим, наконец, программу
. Получив на вход любую программу
, она делает следующее:
- Вычисляет
- Если оказалось, что
не останавливается,
немедленно останавливается
- Иначе вызывает бесконечный цикл
Таким образом, для любой программы p,
останавливается тогда и только тогда, когда
не останавливается. Подставляя
, получаем, что
останавливается тогда и только тогда, когда
не останавливается. Противоречие.
Примечания
- ↑ 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.
Категории:- Математическая логика
- Теория алгоритмов
- Теоремы
- вычисляет
Wikimedia Foundation. 2010.