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

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

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

Источник: Википедия

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я