Теорема о рекурсии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример использования)
(Теорема о рекурсии)
Строка 9: Строка 9:
 
Приведем конструктивное доказательство теоремы.
 
Приведем конструктивное доказательство теоремы.
 
Пусть есть вычислимая <tex>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. <br> Предположим, что у нас в распоряжении есть функция <tex>\mathrm{getSrc()}</tex>, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
 
Пусть есть вычислимая <tex>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. <br> Предположим, что у нас в распоряжении есть функция <tex>\mathrm{getSrc()}</tex>, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
 
+
  '''function''' p(y) {
<code><font size = "3em">
+
    V(x, y) {  
  p(y){  
+
      ...
      V(x,y) {...}
+
    }
 
   
 
   
      main() {
+
    main() {
          return V(getSrc(), y)
+
      '''return''' V(getSrc(), y)
      }
+
    }
 
+
      string getSrc() {...}
+
    getSrc() {  
  }
+
      ...
</font></code>
+
    }
 +
}
 
Теперь нужно определить функцию <tex>\mathrm{getSrc()}</tex>. Предположим, что внутри <tex>p(y)</tex> мы можем определить функцию <tex>\mathrm{getOtherSrc()}</tex>, состоящую из одного оператора <tex>return</tex>, которая вернет весь предшествующий ей код. Тогда <tex>p(y)</tex> перепишется так.  
 
Теперь нужно определить функцию <tex>\mathrm{getSrc()}</tex>. Предположим, что внутри <tex>p(y)</tex> мы можем определить функцию <tex>\mathrm{getOtherSrc()}</tex>, состоящую из одного оператора <tex>return</tex>, которая вернет весь предшествующий ей код. Тогда <tex>p(y)</tex> перепишется так.  
<code><font size = "3em">
+
'''function''' p(y) {
  p(y){  
+
    V(x, y) {
      V(x,y) {...}
+
      ...
 +
    }
 +
 +
    main() {
 +
      '''return''' V(getSrc(), y)
 +
    }
 
   
 
   
      main() {
+
    '''string''' getSrc() {
          return V(getSrc(), y)
+
      '''string''' src = getOtherSrc()
      }
+
      '''return''' src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
 
+
    }
      string getSrc() {
+
}
          string src = getOtherSrc();
 
          return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
 
      }
 
 
 
      string getOtherSrc() {...}  
 
  }
 
</font></code>
 
 
 
 
Теперь <tex>\mathrm{getOtherSrc()}</tex> определяется очевидным образом, и мы получаем '''итоговую версию''' функции <tex>p(y)</tex>
 
Теперь <tex>\mathrm{getOtherSrc()}</tex> определяется очевидным образом, и мы получаем '''итоговую версию''' функции <tex>p(y)</tex>
<code><font size = "3em">
+
'''function''' p(y) {
  p(y){  
+
    V(x, y) {
      V(x,y) {...}
+
      ...
 +
    }
 
   
 
   
      main() {
+
    main() {
          return V(getSrc(), y)
+
      '''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() {
+
    '''string''' getSrc() {
                          return V(getSrc(), y)
+
      '''string''' src = getOtherSrc()
                      }
+
      '''return''' src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
 
+
    }
                      string getSrc() {
+
}
                          string src = getOtherSrc();
 
                          return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
 
                  }";
 
      }  
 
  }
 
</font></code>
 
 
 
 
}}
 
}}
 
Если говорить неформально, теорема о рекурсии утверждает, что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
 
Если говорить неформально, теорема о рекурсии утверждает, что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.

Версия 22:09, 14 декабря 2016

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

Теорема (Клини, о рекурсии / Kleene's recursion theorem):
Пусть [math]V(n, x)[/math]вычислимая функция. Тогда найдётся такая вычислимая [math]p[/math], что [math]\forall y[/math] [math]p(y) = V(p, y)[/math].
Доказательство:
[math]\triangleright[/math]

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

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

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

   getSrc() { 
      ...
   }
}

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

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

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

   string getSrc() {
      string src = getOtherSrc()
      return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
   }
}

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

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

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

   string getSrc() {
      string src = getOtherSrc()
      return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
   }
}
[math]\triangleleft[/math]

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

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

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

Введем на множестве натуральных чисел следующее отношение: [math]x \equiv y \Leftrightarrow U_x = U_y[/math] и докажем вспомогательную лемму.

Определение:
Функция [math]g[/math] называется [math]\equiv[/math] — продолжением функции [math]f[/math], если для всех таких [math]x[/math], что [math]f(x)[/math] определено, [math]g(x) \equiv f(x)[/math].
Лемма:
Для всякой вычислимой функции [math]f[/math] существует вычислимая и всюду определенная функция [math]g[/math], являющаяся ее [math]\equiv[/math] — продолжением.
Доказательство:
[math]\triangleright[/math]

Рассмотрим вычислимую функцию от двух аргументов [math] V(n, x) = U(f(n), x)[/math]. Так как [math]V[/math] — вычислимая, то существует вычислимая и всюду определенная функция [math]s(n)[/math] такая, что: [math]V(n, x) = U(s(n), x)[/math].

Покажем, что [math]s(n)[/math] будет являться [math]\equiv[/math] — продолжением функции [math]f(n)[/math]. Если [math]f(n)[/math] определено, то [math]s(n)[/math] вернет другой номер той же вычислимой функции. Если же [math]f(n)[/math] не определено, то [math]s(n)[/math] вернет номер нигде не определенной функции.

Таким образом, мы нашли [math]\equiv[/math] — продолжение для произвольно взятой вычислимой функции [math]f[/math].
[math]\triangleleft[/math]
Теорема (Роджерс, о неподвижной точке / Rogers' fixed-point theorem):
Пусть [math]U[/math]универсальная функция для класса вычислимых функций одного аргумента, [math]h[/math] — всюду определённая вычислимая функция одного аргумента. Тогда найдется такое [math]n[/math], что [math]U_n=U_{h(n)}[/math], то есть [math]n[/math] и [math]h(n)[/math] - номера одной функции.
Доказательство:
[math]\triangleright[/math]

Будем доказывать теорему от противного: предположим, что существует всюду определенная вычислимая функция [math]h[/math], такая, что [math]U_n \neq U_{h(n)}[/math] для любого [math]n[/math]. В терминах введенного нами отношения, это значит, что [math]h[/math] не имеет [math]\equiv[/math] — неподвижных точек.

Рассмотрим некоторую вычислимую функцию, от которой никакая вычислимая функция не может отличаться всюду. Такой будет, например [math]f(x) = U(x, x)[/math] (действительно, если предположить, что существует вычислимая функция [math]g(n)[/math], всюду отличная от [math]f(n) = U(n, n)[/math], то нарушается определение универсальной функции.)

Согласно доказанной нами лемме, существует вычислимая и всюду определенная функция [math]g(x)[/math], являющаяся [math]\equiv[/math] — продолжением функции [math]f(x)[/math]. Давайте зададим функцию [math]t(x)[/math] следующим образом: [math]t(x) = h(g(x))[/math], где [math]h(x)[/math] - искомая всюду определенная, вычислимая функция, не имеющая [math]\equiv[/math] — неподвижных точек. Тогда [math]t(x)[/math] всюду отличается от [math]f(x)[/math] (в силу того, что [math]h(x)[/math] не имеет неподвижных точек.) Получили противоречие, из чего следует, что такой функции [math]h[/math] не существует.
[math]\triangleleft[/math]

См. также

Источники

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