Изменения
→Примитивно рекурсивные функции
<tex> mod(x,y) = sub(x,mul(y,divide(x,y))) </tex>
=== Теорема о примитивной рекурсивности вычислимых функций ===
==Теорема о рекурсии==
{{Теорема
|id=th1
|about=О рекурсии
|statement= Пусть <tex>V(n, x)</tex> {{---}} вычислимая функция. Тогда найдётся такая вычислимая <tex>p</tex>, что <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>.
|proof=
Приведем конструктивное доказательство теоремы.
Пусть есть вычислимая <tex>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. <br> Предположим, что у нас в распоряжении есть функция <tex>getSrc()</tex>, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
<code><font size = "3em">
p(y){
V(x,y) {...}
main() {
return V(getSrc(), y)
}
string getSrc() {...}
}
</font></code>
Теперь нужно определить функцию <tex>getSrc()</tex>. Предположим, что внутри <tex>p(y)</tex> мы можем определить функцию <tex>getOtherSrc()</tex>, состоящую из одного оператора <tex>return</tex>, которая вернет весь предшествующий ей код. Тогда <tex>p(y)</tex> перепишется так.
<code><font size = "3em">
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() {...}
}
</font></code>
Теперь <tex>getOtherSrc()</tex> определяется очевидным образом, и мы получаем '''итоговую версию''' функции <tex>p(y)</tex>
<code><font size = "3em">
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" + "}";
}";
}
}
</font></code>
}}
Если говорить неформально, теорема о рекурсии утверждает, что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
Приведем так же альтернативую формулировку теоремы и альтернативное (неконструктивное) доказательство.
{{Теорема
|about=о неподвижной точке, Клини
|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]], <tex>h</tex> {{---}} всюду определённая [[Вычислимые_функции|вычислимая функция]]. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>.
Другими словами: нельзя найти алгоритма, преобразующего про-
граммы, который бы по каждой программе давал другую (не эквива-
лентную ей).
|proof=
Начнём с доказательства леммы.
{{Лемма
|statement= Пусть на натуральных числах задано отношение эквивалентности <tex>\equiv</tex>. Тогда следующие два утверждения не могут быть выполнены одновременно: <br>
# Пусть <tex>f</tex> {{---}} вычислимая функция. Тогда существует всюду определённое вычислимое <tex>\equiv</tex> {{---}} продолжение <tex>g</tex> функции <tex>f</tex>, то есть такая <tex>g</tex>, что <tex>D(g)=N</tex> и <tex>\forall x</tex> такого, что <tex>f(x) \ne \perp</tex>, выполнено <tex>f(x) \equiv g(x)</tex>.
# Найдётся такая всюду определенная вычислимая <tex>h</tex>, что <tex>\forall n </tex> выполнено <tex>h(n) \not\equiv n</tex>.
|proof=
Приведем доказательство от противного. Пусть оба утверждения выполнены. <br>
Определим функцию <tex>f</tex> так: <tex>f(x)=U(x,x)</tex>. Заметим, что никакая всюду вычислимая функция не отличается от <tex>f</tex> всюду. <br> Согласно первому утверждению найдётся всюду определённое вычислимое <tex>\equiv</tex> {{---}} продолжение <tex>g</tex> функции <tex>f</tex>. <br> Определим функцию <tex>t</tex> так: <tex>t(x)=h(g(x))</tex>, где <tex>h</tex> {{---}} функция из второго утверждения. <br >Если <tex>f(x) \ne \perp</tex>, то <tex>f(x)=g(x) \ne h(g(x))=t(x)</tex>, то есть <tex>f(x) \ne t(x)</tex>. Если <tex>f(x)= \perp</tex>, то <tex>f(x) \ne t(x)</tex>, так как <tex>t</tex> всюду определена. Значит, <tex>f</tex> всюду отлична от <tex>t</tex>, получили противоречие.
}}
Теперь определим отношение <tex>\equiv</tex> так: <tex>x \equiv y \Leftrightarrow U_x = U_y</tex>. Покажем, что для него выполнено первое утверждение леммы. <br> Для заданной <tex>f</tex> определим <tex>V(n,x) = U(f(n), x)</tex>. <br> Так как <tex>U</tex> {{---}} универсальная функция, то найдётся такая всюду определенная вычислимая функция <tex>s</tex>, что <tex>V(n,x) = U(s(n), x)</tex>. <br> Тогда <tex>\forall x </tex> и <tex> n </tex> будет выполнено <tex>U(f(n), x) = U(s(n), x)</tex>. Значит, <tex>\forall n </tex> <tex> s(n) \equiv f(n)</tex>, то есть <tex>s</tex> {{---}} всюду определенное <tex>\equiv</tex> {{---}} продолжение <tex>f</tex>.
Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного <tex>h</tex> <tex> \exists n</tex> такое, что <tex>U_{h(n)} = U_n</tex>.
}}
