Теорема о рекурсии

Теорема о рекурсии

Теорема (О рекурсии):

Пусть [math]U[/math] - универсальная функция, [math]h[/math] - всюду определенная вычислимая функция. Тогда найдется такое [math]n[/math], что [math]U_n=U_{h(n)}[/math]

Доказательство:

[math]\triangleright[/math]

Начнем с доказательства леммы. Лемма: Пусть на натуральных числах задано отношение эквивалентности [math]\equiv[/math]. Тогда следущие два утверждения не могут быть выполнены одновременно: Пусть [math]f[/math] - вычислимая функция. Тогда существует всюду определенное вычислимое [math]\equiv[/math]-продолжение [math]g[/math] функции [math]f[/math], т.е. такая [math]g[/math] что [math]D(g)=N[/math] и [math]\forall x[/math] такого что [math]f(x) \ne \perp[/math] выполнено [math]f(x) \equiv g(x)[/math] Найдется такая всюду определенная вычислимая [math]h[/math] что [math]\forall n [/math] [math]h(n) \not\equiv n[/math] Доказательство: [math]\triangleright[/math] От противного. Пусть оба утверждения выполнены. Определим функцию [math]f[/math] так: [math]f(x)=U(x,x)[/math]. Заметим что никакая всюду вычислимая функция не отличается от [math]f[/math] всюду. Согласно первому утверждению найдется всюду определенное вычислимое [math]\equiv[/math]-продолжение [math]g[/math] функции [math]f[/math]. Определим функцию [math]t[/math] так: [math]t(x)=h(g(x))[/math], где [math]h[/math] - функция из второго утверждения. Если [math]f(x) \ne \perp[/math], то [math]f(x)=g(x) \ne h(g(x))=t(x)[/math], т.е. [math]f(x) \ne t(x)[/math]. Если [math]f(x)= \perp[/math], то [math]f(x) \ne t(x)[/math], т.к. [math]f[/math] - всюду определена. Значит [math]f[/math] всюду отлична от [math]t[/math], противоречие. [math]\triangleleft[/math]

[math]\triangleleft[/math]

Источники

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