Изменения
→Теорема о неподвижной точке
|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=
{{Лемма
|statement= Пусть на натуральных числах задано отношение эквивалентности Для всякой вычислимой функции <tex>\equivf</tex>. Тогда следующие два утверждения не могут быть выполнены одновременно: <br># Пусть существует вычислимая и всюду определенная функция <tex>fg</tex> {{---}} вычислимая функция. Тогда существует всюду определённое вычислимое , являющаяся ее <tex>\equiv</tex> {{---}} продолжение <tex>g</tex> функции продолжением (это значит, что если <tex>f(n)</tex>определено, то есть такая <tex>g</tex>, что <tex>D(gn)=N</tex> и <tex>\forall x</tex> такого, что <tex>equiv f(xn) \ne \perp</tex>, выполнено ).|proof= Рассмотрим вычислимую функцию от двух аргументов <tex>fV(n, x) \equiv g= U(f(n), x)</tex>.# Найдётся такая всюду определенная вычислимая Так как <tex>hV</tex>— вычислимая, что то существует вычислимая и всюду определенная функция <tex>\forall n </tex> выполнено <tex>hs(n) \not\equiv n</tex>.|proof=Приведем доказательство от противного. Пусть оба утверждения выполнены. <br>Определим функцию <tex>f</tex> тактакая, что: <tex>fV(n, x)=U(xs(n),x)</tex>. Заметим Покажем, что никакая всюду вычислимая функция не отличается от <tex>fs(n)</tex> всюду. <br> Согласно первому утверждению найдётся всюду определённое вычислимое будет являться <tex>\equiv</tex> {{---}} продолжение <tex>g</tex> продолжением функции <tex>f</tex>. <br> Определим функцию <tex>t</tex> так: <tex>t(x)=h(g(x)n)</tex>, где <tex>h</tex> {{---}} функция из второго утверждения. <br >Если <tex>f(x) \ne \perp</tex>, то <tex>f(x)=g(x) \ne h(g(x))=t(xn)</tex>определено, то есть <tex>fs(x) \ne t(xn)</tex>вернет другой номер той же вычислимой функции. Если же <tex>f(xn)= \perp</tex>не определено, то <tex>fs(x) \ne t(xn)</tex>вернет номер нигде не определенной функции.Таким образом, так как мы нашли <tex>t\equiv</tex> всюду определена. Значит, {{---}} продолжение для произвольно взятой вычислимой функции <tex>f</tex> всюду отлична от <tex>t</tex>, получили противоречие.
}}
}}
==Пример использования==
