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

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

Пусть — универсальная функция, — всюду определенная вычислимая функция. Тогда найдется такое , что

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

Начнем с доказательства леммы.

Утверждение:

Пусть на натуральных числах задано отношение эквивалентности . Тогда следущие два утверждения не могут быть выполнены одновременно:

Пусть [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]\equiv[/math] так: . Покажем, что для него выполнено первое утверждение леммы.
Для заданной [math]f[/math] определим [math]V(n,x) = U(f(n), x)[/math].
Так как [math]U[/math] — универсальная функция, то найдется такая всюду определенная вычислимая [math]s[/math], что [math]V(n,x) = U(s(n), x)[/math].
Тогда [math]\forall x, n [/math] [math]U(f(n), x) = U(s(n), x)[/math], значит [math]\forall n [/math] [math] s(n) \equiv f(n)[/math], то есть [math]s[/math] — всюду определенное [math]\equiv[/math] — продолжение [math]f[/math].

Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного такое что .

Теорему о рекурсии можно переформулировать следущим образом.

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

Пусть — вычислимая функция.Тогда найдется такая вычислимая , что .

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

Так как — универсальная, то для любой вычислимой всюду определенной найдется такая вычислимая всюду определенная , что . Тогда найдется такая что .
По доказанному найдется такое что .
Возьмем . Тогда .

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

Пример использования

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

Утверждение:

Язык неразрешим.

Предположим обратное, тогда существует программа [math]r[/math] разрещающая [math]L[/math]. Рассмотрим следущую программу:


p(x)
  if r(p)
     return 1
  while true

Пусть . Тогда условие выполняется и . Противоречие. Если , то не выполняется и . Противоречие.

Источники

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

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