Изменения

|about=О о рекурсии|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]], <tex>h</tex> {{---}} всюду определенная определённая [[Вычислимые_функции|вычислимая функция]]. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>.

Начнем Начнём с доказательства леммы.{{Утверждение|id=st1Лемма|statement= Пусть на натуральных числах задано отношение эквивалентности <tex>\equiv</tex>. Тогда следущие следующие два утверждения не могут быть выполнены одновременно: <br>* # Пусть <tex>f</tex> {{---}} вычислимая функция. Тогда существует всюду определенное определённое вычислимое <tex>\equiv</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) \equiv g(x)</tex>.* Найдется # Найдётся такая всюду определенная вычислимая <tex>h</tex> , что <tex>\forall n </tex> <tex>h(n) \not\equiv n</tex>.

От Приведем доказательство от противного. Пусть оба утверждения выполнены. <br>Определим функцию <tex>f</tex> так: <tex>f(x)=U(x,x)</tex>. Заметим , что никакая всюду вычислимая функция не отличается от <tex>f</tex> всюду. <br> Согласно первому утверждению найдется найдётся всюду определенное определённое вычислимое <tex>\equiv</tex> {{---}} продолжение <tex>g</tex> функции <tex>f</tex>. <br> Определим функцию <tex>t</tex> так: <tex>t(x)=h(g(x))</tex>, где <tex>h</tex> {{---}} функция из второго утверждения. <br >Если <tex>f(x) \ne \perp</tex>, то <tex>f(x)=g(x) \ne h(g(x))=t(x)</tex>, т.е. то есть <tex>f(x) \ne t(x)</tex>. Если <tex>f(x)= \perp</tex>, то <tex>f(x) \ne t(x)</tex>, т.к. так как <tex>t</tex> {{---}} всюду определена. Значит , <tex>f</tex> всюду отлична от <tex>t</tex>, получили противоречие.

Теперь определим отношение <tex>\equiv</tex> так: <tex>x \equiv y \Leftrightarrow U_x = U_y</tex>. Покажем, что для него выполнено первое утверждение леммы. <br> Для заданной <tex>f</tex> определим <tex>V(n,x) = U(f(n), x)</tex>. <br> Так как <tex>U</tex> {{---}} универсальная функция, то найдется найдётся такая всюду определенная вычислимая <tex>s</tex>, что <tex>V(n,x) = U(s(n), x)</tex>. <br> Тогда <tex>\forall x, n </tex> <tex>U(f(n), x) = U(s(n), x)</tex>. Значит, значит <tex>\forall n </tex> <tex> s(n) \equiv f(n)</tex>, то есть <tex>s</tex> {{---}} всюду определенное <tex>\equiv</tex> {{---}} продолжение <tex>f</tex>.Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного <tex>h</tex> <tex> \exists n</tex> такое , что <tex>U_{h(n)} = U_n</tex>.

Неформально Если говорить неформально, теорема о рекурсии утверждает то , что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.

Используя теорему о рекурсии приведем приведём простое доказательство неразрешимости языка <tex>L=\{p|p(\epsilon)=\perp\}</tex>.

== Литература ==* ''Верещагин Н. К. Верещагин, Шень А. Шень. '' '''Лекции по математической логике и теории алгоритмовалгоритов. Часть 3. Вычислимые функции. -- ''' — М.: МЦНМО, 1999- С. 176