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

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

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

Что читатель, сложно? Сейчас поясню проще. Если доказать, что теорема Райса не верна для определенных условий (которые еще нужно определить), то можно ответить, как появилась Вселенная и кто такой Бог. И за это решение «английские ученые» предлагают один миллион долларов? Господа, зная решение алгоритмически неразрешимых задач, можно говорить о собственном бессмертии и возможности познать божественное! ... " 

Комментарии: