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

Теорема (Клини, о рекурсии / Kleene's recursion theorem):

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

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

Приведем конструктивное доказательство теоремы. Пусть есть вычислимая [math]V(x,y)[/math]. Будем поэтапно строить функцию [math]p(y)[/math].
Предположим, что у нас в распоряжении есть функция [math]getSrc()[/math], которая вернет код [math]p(y)[/math]. Тогда саму [math]p(y)[/math] можно переписать так:

p(y){ 
     V(x,y) {...}

     main() {
         return V(getSrc(), y)
     }
 
     string getSrc() {...}
 }

Теперь нужно определить функцию [math]getSrc()[/math]. Предположим, что внутри [math]p(y)[/math] мы можем определить функцию [math]getOtherSrc()[/math], состоящую из одного оператора [math]return[/math], которая вернет весь предшествующий ей код. Тогда [math]p(y)[/math] перепишется так.

 p(y){ 
     V(x,y) {...}

     main() {
         return V(getSrc(), y)
     }
 
     string getSrc() {
         string src = getOtherSrc();
         return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
     }
 
     string getOtherSrc() {...} 
 }

Теперь [math]getOtherSrc()[/math] определяется очевидным образом, и мы получаем итоговую версию функции [math]p(y)[/math]

 p(y){ 
     V(x,y) {...}

     main() {
         return V(getSrc(), y)
     }
 
     string getSrc() {
         string src = getOtherSrc();
         return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
     }
 
     string getOtherSrc() {
         return "  p(y){             // Возвращаем весь предыдущий код
                    V(x,y) {...}

                     main() {
                         return V(getSrc(), y)
                     }
 
                     string getSrc() {
                         string src = getOtherSrc();
                         return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
                 }";
     } 
 }

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

Приведем так же альтернативую формулировку теоремы и альтернативное (неконструктивное) доказательство.

Теорема о неподвижной точке

Теорема (Роджерс, о неподвижной точке / Rogers' fixed-point theorem):

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

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

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

Лемма:

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

Пусть [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 [/math] и [math] 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

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

Доказательство теоремы Успенского-Райса с использованием теоремы о рекурсии:

Теорема:

Язык никакого нетривиального свойства не является разрешимым.

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

Пусть . Предположим, что язык свойства [math]F[/math] разрешается программой [math]d[/math]. Пусть [math]f \in L(F), g \not\in L(F)[/math]. Напишем следующую программу:

Q(x,y)
  if d(x)
    return g(y)
  else
    return f(y)

По теореме о рекурсии, .

Если [math]p \in L(F)[/math], то .

Если же [math]p \not\in L(F)[/math], то .

В обоих случаях получаем противоречие.

Источники

Wikipedia — Kleene's recursion theorem
Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 - С. 176
Kleene, Stephen On notation for ordinal numbers - The Journal of Symbolic Logic, 1938 - С. 150-155

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