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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 26: Строка 26:
 
Так как <tex>U</tex> {{---}} универсальная, то для любой вычислимой всюду определенной <tex>n</tex> найдется такая вычислимая всюду определенная <tex>num</tex>, что <tex>n=U_{num(n)}</tex>. Тогда найдется такая <tex>h</tex>, что <tex>\forall n, x</tex> <tex>V(n, x) = U(h(num(n)), x)</tex>. <br >По доказанному найдется такое <tex>n_0</tex>, что <tex>U_{n_0} = U_{h(n_0)}</tex>. <br> Возьмем <tex>p=U_{n_0}</tex>. Тогда <tex>V(p, x) = V(U_{n_0}, x) = U(h(num(U_{n_0})), x) = U(h(n_0), x) = U(n_0, x) = p(x)</tex>.
 
Так как <tex>U</tex> {{---}} универсальная, то для любой вычислимой всюду определенной <tex>n</tex> найдется такая вычислимая всюду определенная <tex>num</tex>, что <tex>n=U_{num(n)}</tex>. Тогда найдется такая <tex>h</tex>, что <tex>\forall n, x</tex> <tex>V(n, x) = U(h(num(n)), x)</tex>. <br >По доказанному найдется такое <tex>n_0</tex>, что <tex>U_{n_0} = U_{h(n_0)}</tex>. <br> Возьмем <tex>p=U_{n_0}</tex>. Тогда <tex>V(p, x) = V(U_{n_0}, x) = U(h(num(U_{n_0})), x) = U(h(n_0), x) = U(n_0, x) = p(x)</tex>.
 
}}
 
}}
 +
Можно привести '''конструктивное доказательство''' этой теоремы: <br>
 +
Пусть есть вычислимая <tex>V(x,y)</tex>. Введем вспомогательную функцию <tex>getSrc()</tex> следующим образом: <br>
 +
<code> <font size = "3em">
 +
  getSrc(){
 +
      "p(y) {\n    return V(getSrc(), y)\n}";
 +
  }
 +
</font> </code>
 +
И определим функцию <tex>p(y)</tex> так:
 +
<code> <font size = "3em">
 +
  p(y){
 +
      return V(getSrc(), y)
 +
  }
 +
</font> </code>
 +
Заметим, что функция <tex>getSrc()</tex> возвращает код функции <tex>p(y)</tex>, значит <tex>p(y)</tex> удовлетворяет требованию <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>. <br>
 
Если говорить неформально, теорема о рекурсии утверждает, что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
 
Если говорить неформально, теорема о рекурсии утверждает, что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
  

Версия 23:32, 23 января 2012

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

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

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

Лемма:
Пусть на натуральных числах задано отношение эквивалентности [math]\equiv[/math]. Тогда следующие два утверждения не могут быть выполнены одновременно:
  1. Пусть [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].
  2. Найдётся такая всюду определенная вычислимая [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]t[/math] всюду определена. Значит, [math]f[/math] всюду отлична от [math]t[/math], получили противоречие.
[math]\triangleleft[/math]

Теперь определим отношение [math]\equiv[/math] так: [math]x \equiv y \Leftrightarrow U_x = U_y[/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]h[/math] [math] \exists n[/math] такое, что [math]U_{h(n)} = U_n[/math].
[math]\triangleleft[/math]

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

Теорема (О рекурсии):
Пусть [math]V(n, x)[/math] — вычислимая функция.Тогда найдется такая вычислимая [math]p[/math], что [math]\forall y[/math] [math]p(y) = V(p, y)[/math].
Доказательство:
[math]\triangleright[/math]
Так как [math]U[/math] — универсальная, то для любой вычислимой всюду определенной [math]n[/math] найдется такая вычислимая всюду определенная [math]num[/math], что [math]n=U_{num(n)}[/math]. Тогда найдется такая [math]h[/math], что [math]\forall n, x[/math] [math]V(n, x) = U(h(num(n)), x)[/math].
По доказанному найдется такое [math]n_0[/math], что [math]U_{n_0} = U_{h(n_0)}[/math].
Возьмем [math]p=U_{n_0}[/math]. Тогда [math]V(p, x) = V(U_{n_0}, x) = U(h(num(U_{n_0})), x) = U(h(n_0), x) = U(n_0, x) = p(x)[/math].
[math]\triangleleft[/math]

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

 getSrc(){
     "p(y) {\n    return V(getSrc(), y)\n}";
 }

И определим функцию [math]p(y)[/math] так:

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

Заметим, что функция [math]getSrc()[/math] возвращает код функции [math]p(y)[/math], значит [math]p(y)[/math] удовлетворяет требованию [math]\forall y[/math] [math]p(y) = V(p, y)[/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]

Источники

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