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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Теорема о рекурсии)
(→‎Теорема о неподвижной точке)
Строка 75: Строка 75:
  
 
==Теорема о неподвижной точке==
 
==Теорема о неподвижной точке==
−
{{Теорема
 
−
|id=th2
 
−
|author=Роджерс
 
−
|about=о неподвижной точке / ''Rogers' fixed-point theorem''
 
−
|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]] для класса вычислимых функций одного аргумента, <tex>h</tex> {{---}} всюду определённая [[Вычислимые_функции|вычислимая функция]] одного аргумента. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>, то есть <tex>n</tex> и <tex>h(n)</tex> - номера одной функции.
 
−
|proof=
 
 
Введем на множестве натуральных чисел следующее отношение: <tex>x \equiv y \Leftrightarrow U_x = U_y</tex> и докажем вспомогательную лемму.
 
Введем на множестве натуральных чисел следующее отношение: <tex>x \equiv y \Leftrightarrow U_x = U_y</tex> и докажем вспомогательную лемму.
 
{{Лемма
 
{{Лемма
Строка 89: Строка 83:
 
Таким образом, мы нашли <tex>\equiv</tex> {{---}} продолжение для произвольно взятой вычислимой функции <tex>f</tex>.
 
Таким образом, мы нашли <tex>\equiv</tex> {{---}} продолжение для произвольно взятой вычислимой функции <tex>f</tex>.
 
}}
 
}}
 +
{{Теорема
 +
|id=th2
 +
|author=Роджерс
 +
|about=о неподвижной точке / ''Rogers' fixed-point theorem''
 +
|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]] для класса вычислимых функций одного аргумента, <tex>h</tex> {{---}} всюду определённая [[Вычислимые_функции|вычислимая функция]] одного аргумента. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>, то есть <tex>n</tex> и <tex>h(n)</tex> - номера одной функции.
 +
|proof=
 
Будем доказывать теорему от противного: предположим, что существует всюду определенная вычислимая функция <tex>h</tex>, такая, что <tex>U_n \neq U_{h(n)}</tex> для любого <tex>n</tex>. В терминах введенного нами отношения, это значит, что <tex>h</tex> не имеет <tex>\equiv</tex> {{---}} неподвижных точек.  
 
Будем доказывать теорему от противного: предположим, что существует всюду определенная вычислимая функция <tex>h</tex>, такая, что <tex>U_n \neq U_{h(n)}</tex> для любого <tex>n</tex>. В терминах введенного нами отношения, это значит, что <tex>h</tex> не имеет <tex>\equiv</tex> {{---}} неподвижных точек.  
  

Версия 21:05, 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] можно переписать так: 

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

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

Теперь нужно определить функцию [math]\mathrm{getSrc()}[/math]. Предположим, что внутри [math]p(y)[/math] мы можем определить функцию [math]\mathrm{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]\mathrm{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" + "}";
                 }";
     } 
 }
[math]\triangleleft[/math]

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

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

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

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

Лемма:
Для всякой вычислимой функции [math]f[/math] существует вычислимая и всюду определенная функция [math]g[/math], являющаяся ее [math]\equiv[/math] — продолжением (это значит, что если [math]f(n)[/math] определено, то [math]g(n) \equiv f(n)[/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]

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

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

Лемма:
Язык [math]L=\{p|p(\epsilon)=\perp\}[/math] неразрешим.
Доказательство:
[math]\triangleright[/math]

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

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

Пусть [math]p(\epsilon)=\perp[/math]. Тогда условие [math]r(p)[/math] выполняется и [math]p(\epsilon)=1[/math]. Противоречие. Если [math]p(\epsilon) \ne \perp[/math], то [math]r(p)[/math] не выполняется и [math]p(\epsilon)=\perp[/math]. Противоречие.
[math]\triangleleft[/math]

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

Теорема:
Язык никакого нетривиального свойства не является разрешимым.
Доказательство:
[math]\triangleright[/math]

Пусть [math]F \subset RE, \varnothing \not= F \not= RE[/math]. Предположим, что язык свойства [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]\exists p \; \forall y \; p(y) = Q(p,y)[/math].

Если [math]p \in L(F)[/math], то [math]Q(p,y) = g(y) \Rightarrow p(y) = g(y) \Rightarrow p \not\in L(F)[/math].

Если же [math]p \not\in L(F)[/math], то [math]Q(p,y) = f(y) \Rightarrow p(y) = f(y) \Rightarrow p \in L(F)[/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
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_рекурсии&oldid=57826»