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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 25: Строка 25:
 
|statement= Пусть <tex>V(n, x)</tex> - вычислимая функция.Тогда найдется такая вычислимая <tex>p</tex>, что <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>
 
|statement= Пусть <tex>V(n, x)</tex> - вычислимая функция.Тогда найдется такая вычислимая <tex>p</tex>, что <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>
 
|proof=
 
|proof=
Так как <tex>U</tex> - универсальная, то найдется вычислимая всюду определенная <tex>h</tex> такая что <tex>\forall n, x</tex> <tex>V(n, x) = U(h(n), x)</tex>. По доказанному найдется такое <tex>n_0</tex> что <tex>U_{n0} = U_{h(n0)}</tex>. Тогда <tex>V(n0, x) = U(h(n0), x) = U(n0, x)</tex>. Взяв <tex>p=U_{n0}</tex> получаем требуемое утверждение.
+
Так как <tex>U</tex> - универсальная, то найдется вычислимая всюду определенная <tex>h</tex> такая что <tex>\forall n, x</tex> <tex>V(n, x) = U(h(n), x)</tex>. <br >По доказанному найдется такое <tex>n_0</tex> что <tex>U_{n0} = U_{h(n_0)}</tex>. <br> Тогда <tex>V(n_0, x) = U(h(n_0), x) = U(n_0, x)</tex>. Взяв <tex>p=U_{n_0}</tex> получаем требуемое утверждение.
 +
}}
 +
Неформально теорема о рекурсии утверждает то что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
 +
==Пример==
 +
Используя теорему о рекурсии приведем простое доказательство неразрешимости языка <tex>L=\{p|p(\epsilon)=\perp\}</tex>
 +
{{Утверждение
 +
|id=st2
 +
|statement= Язык <tex>L=\{p|p(\epsilon)=\perp\}</tex> неразрешим.
 +
|proof=
 +
Предположим обратное, тогда существует программа <tex>r</tex> разрещающая <tex>L</tex>.
 +
Рассмотрим следущую программу
 +
<code>
 +
p(x)
 +
  if r(p)
 +
      return 1
 +
  while true
 +
</code>
 +
Пусть <tex>p(\epsilon)=\perp</tex>. Тогда условие <tex>r(p)</tex> выполняется и <tex>p(\epsilon)=1</tex>. Противоречие. Если <tex>p(\epsilon) \ne \perp</tex>, то <tex>r(p)</tex> не выполняется и <tex>p(\epsilon)=\perp</tex>. Противоречие.
 
}}
 
}}
  
 
==Источники==
 
==Источники==
 
Н. К. Верещагин,  А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
 
Н. К. Верещагин,  А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999

Версия 11:58, 29 декабря 2011

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

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

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

Утверждение:
Пусть на натуральных числах задано отношение эквивалентности [math]\equiv[/math]. Тогда следущие два утверждения не могут быть выполнены одновременно:
  • Пусть [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]\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, 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]h[/math] такая что [math]\forall n, x[/math] [math]V(n, x) = U(h(n), x)[/math].
По доказанному найдется такое [math]n_0[/math] что [math]U_{n0} = U_{h(n_0)}[/math].
Тогда [math]V(n_0, x) = U(h(n_0), x) = U(n_0, x)[/math]. Взяв [math]p=U_{n_0}[/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]

Источники

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