69
правок
Изменения
Нет описания правки
|statement= Пусть <tex>U</tex> - [[Диагональный_метод|универсальная функция]], <tex>h</tex> - всюду определенная [[Вычислимые_функции|вычислимая функция]]. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>
|proof=
Начнем с доказательства леммы.{{Лемма|id=st1|statement= Пусть на натуральных числах задано отношение эквивалентности <tex>\simeq</tex>. Тогда следущие два утверждения не могут быть выполнены одновременно: <br>* Пусть <tex>f</tex> - вычислимая функция. Тогда существует всюду определенное вычислимое <tex>\simeq</tex>-продолжение <tex>g</tex> функции <tex>f</tex>, т.е. такая <tex>g</tex> что <tex>D(g)=N</tex> и <tex>\forall x</tex> такого что <tex>f(x) \ne \perp</tex> выполнено <tex>f(x) \simeq g(x)</tex> * Найдется такая всюду определенная вычислимая <tex>h</tex> что <tex>\forall n </tex> <tex>h(n) \ne n</tex>|proof=Ололо}}
}}
