Изменения

|id=th1|about=О рекурсии|statement= Пусть Если для вычислимой функции <tex>V(n, x)F </tex> {{---}} вычислимая существует примитивно рекурсивная функция. Тогда найдётся такая вычислимая <tex>pT </tex>, такая что для любого входа <tex>\forall yx </tex> максимальное количество за которое будет посчитана <tex>pF(yx) = V</tex> на MT равно <tex> T(px) </tex>, y)то <tex> F </tex> примитивно рекурсивная функция.

Приведем конструктивное доказательство теоремы.Пусть есть вычислимая <tex>V(xКаждому состоянию MT поставим в соответствие список из четырех чисел [L,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. <br> ПредположимR, что у нас в распоряжении есть функция <tex>getSrc()</tex>S, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так: <code><font size = "3em"> p(y){ V(xC],y) {...} main() { return V(getSrc(), y) } string getSrc() {...} }</font></code>гдеТеперь нужно определить функцию <tex>getSrc()L </tex>. Предположим- состояние MT слева от головки ленты, что внутри <tex>p(y)</tex> мы можем определить функцию <tex>getOtherSrc()</tex>, состоящую из одного оператора <tex>return</tex>представлено в виде числа в системы счисления с основанием равным алфавиту MT, которая вернет весь предшествующий ей кодчисло записано слева направо. Тогда <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()R </tex> определяется очевидным образом- состояние MT справа от головки, и мы получаем '''итоговую версию''' функции представлено аналогично <tex>p(y)L </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>US </tex> {{---}} [[Диагональный_метод|универсальная функция]], номер текущего состояния<tex>hC </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)C </tex>. Заметимзаписывается новый символ, что никакая всюду вычислимая функция не отличается от <tex>f</tex> всюду. <br> Согласно первому утверждению найдётся всюду определённое вычислимое <tex>\equiv</tex> {{затем из---}} продолжение за сдвига головки а <tex>gL </tex> функции и <tex>f</tex>. <br> Определим функцию <tex>t</tex> так: <tex>t(x)=h(g(x))R </tex>, где <tex>h</tex> {{---}} функция из второго утверждения. <br >Если <tex>f(x) \ne \perp</tex>в конец добавляется новая цифра или удаляется старая, то затем в <tex>f(x)=g(x) \ne h(g(x))=t(x)C </tex> записываетcя символ после сдвига, то есть и в конце перехода в <tex>f(x) \ne t(x)S </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>, . В силу того что нужный переход можно выбрать используя конечное число функций if следует что <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>тоже примитивно рекурсивная функция.