Изменения
→Теорема о неподвижной точке
|author=Роджерс
|about=о неподвижной точке / ''Rogers' fixed-point theorem''
|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]] для класса вычислимых функций одного аргумента, <tex>h</tex> {{---}} всюду определённая [[Вычислимые_функции|вычислимая функция]] одного аргумента. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>, то есть <tex>n</tex> и <tex>h(n)</tex> - номера одной функции. Другими словами, нельзя найти алгоритма, преобразующего программы, который бы по каждой программе давал другую (не эквивалентную ей).
|proof=
Начнём с доказательства леммы.
Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного <tex>h</tex> <tex> \exists n</tex> такое, что <tex>U_{h(n)} = U_n</tex>.
}}
Другими словами, нельзя найти алгоритма, преобразующего программы, который бы по каждой программе давал другую (не эквивалентную ей).
==Пример использования==
