Изменения
Нет описания правки
|id=th2
|about=о неподвижной точке, Клини
|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]], <tex>h</tex> {{---}} всюду определённая [[Вычислимые_функции|вычислимая функция]]. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>. Другими словами: нельзя найти алгоритма, преобразующего про-граммы, который бы по каждой программе давал другую (не эквива-лентную ей).
|proof=
Начнём с доказательства леммы.
==Источники==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999 - С. 176
* ''Kleene, Stephen'' '''On notation for ordinal numbers''' - The Journal of Symbolic Logic, 1938 - С. 150-155
