Interested Article - Теорема Райса

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

Названа по имени американского математика , доказавшего её в 1951 году в докторской диссертации . Изначально доказана для частично-рекурсивных функций , существует аналог теоремы для рекурсивных множеств .

Примечания

Rice, H. G. (англ.) // Transactions of the American Mathematical Society : journal. — 1953. — March ( vol. 74 , no. 2 ). — P. 358—366 . — doi : . 9 ноября 2014 года.