Меню
Главная
Случайная статья
Настройки
|
Теорема Райса — утверждение теории алгоритмов, согласно которому для любого нетривиального свойства вычислимых функций определение того, вычисляет ли произвольный алгоритм функцию с таким свойством, является алгоритмически неразрешимой задачей. Здесь свойство называется нетривиальным, если существуют и вычислимые функции, обладающие этим свойством, и вычислимые функции, не обладающие им.
Названа по имени американского математика Генри Гордона Райса, доказавшего её в 1951 году в докторской диссертации[1]. Изначально доказана для частично-рекурсивных функций, существует аналог теоремы для рекурсивных множеств.
Примечания
- Rice, H. G. Classes of Recursively Enumerable Sets and Their Decision Problems (англ.) // Transactions of the American Mathematical Society : journal. — 1953. — March (vol. 74, no. 2). — P. 358—366. — doi:10.2307/1990888. Архивировано 9 ноября 2014 года.
Литература
|
|