Загрузка...

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


Никакое нетривиальное свойство вычислимых функций не является алгоритмически разрешимым.ДОКАЗАТЕЛЬСТВО.
A. Переформулируем условие теоремы.
Пусть — некоторый класс вычислимых функций по Тьюрингу, нетривиалных в том смысле, что имеются функции, как принадлежащие классу , так и функции не принадлежащие классу .
Не существует алгоритма, который по описанию некой вычислимой функции определял бы принадлежит ли эта функция некоторому классу , или нет.
B. Предположим, что такой алгоритм существует, тогда алгоритм можно определить так:
, где — некоторая машина Тьюринга, вычисляющая функцию .
C. Построим вспомогательную машину для заданной машины такую, что   нигде не определена.
Такую машину можно построить имея конкретную систему команд машины .
D. Применим полученную машину в качестве исходных данных для машины . Заметим, что заведомо принадлежит классу так как вычисляет функцию , то есть

E. В результате использования конструктивных средств при построении машины получили машину , решающую проблему остановки, что невозможно. Следовательно предположение о существовании машины неверно.
Окончание доказательства.

Замечание. Из теоремы Райса следует, что по описанию вычислимой функции (алгоритма) нельзя узнать является ли эта функция постоянной, периодической, ограниченной, определима ли в конкретной точке ?

Замечание. Теорема Райса связывает такие понятия как алгоритм и вычислимая функция, где алгоритм не тождественен вычислимой функции, то есть по описанию алгоритма (где все понятно и ясно) ничего нельзя сказать о функции, которую он реализует.

Загрузка...