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

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

[править] Формулировка теоремы Райса

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

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

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

Пусть - некоторое свойство одноместных интуитивно вычислимых функций. Назовем свойство нетривиальным , если в множестве существуют и функции, обладающие этим свойством, и функции, не обладающие им.

Тогда теорему Райса можно переформулировать так:

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

Отсюда следует, в частности, что задача восстановления алгоритма по тексту программы алгоритмически неразрешима.