Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


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

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

Шаблон:Сирота

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

A\subsetЧРФ1, A\ne\empty, A\neЧРФ1, B=\{n: \theta(n)\in A\}, тогда \chi_B\,\! не является ЧРФ.

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

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

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

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

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

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

Викия-сеть

Случайная вики