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

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

Рассмотрим произвольную вычислимую функцию от двух аргументов — [math]V(x, y)[/math]. Теорема о рекурсии утверждает, что всегда можно найти эквивалентную ей [math]p(y) = V(p, y)[/math], которая будет использовать саму себя для вычисления значения. Сформулируем теорему более формально.

Теорема (Клини, о рекурсии / 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]

Приведем конструктивное доказательство теоремы. Введем новые обозначения для псевдокода. Внутри блока program располагаются функции, среди которых есть функция [math]\mathrm{main}[/math]: program int p(int x): ... int main(): ... ... Тогда вызов [math]\mathrm{p(x)}[/math] — вызов функции [math]\ mathrm{main}[/math] от соответствующего аргумента. Символ [math]\$[/math], за которым следует имя переменной (например, [math]\mathrm{\$src}[/math]), используется для интерполяции строк, то есть подстановки значения переменной в строковый литерал. Все входные данные далее можно интерпретировать как строки, поэтому все типы аргументов и возвращаемых значений будут иметь тип string. Пусть есть вычислимая [math]V(x,y)[/math]. Будем поэтапно строить функцию [math]p(y)[/math]. Предположим, что у нас в распоряжении есть функция [math]\mathrm{getSrc()}[/math], которая вернет код [math]p(y)[/math]. Тогда саму [math]p(y)[/math] можно переписать так: program string p(string y): string V(string x, string y): ... string main(): return V(getSrc(), y) string getSrc(): ... Теперь нужно определить функцию [math]\mathrm{getSrc()}[/math]. Предположим, что внутри [math]p(y)[/math] мы можем определить функцию [math]\mathrm{getOtherSrc()}[/math], состоящую из одного оператора [math]\mathrm{return}[/math], которая вернет весь предшествующий ей код. Тогда [math]p(y)[/math] перепишется так. program string p(string y): string V(string x, string y): ... string main(): return V(getSrc(), y) string getSrc(): string src = getOtherSrc() return ```$src string getOtherSrc(): | return src\n``` string getOtherSrc(): ... Теперь [math]\mathrm{getOtherSrc()}[/math] определяется очевидным образом, и мы получаем итоговую версию функции [math]p(y)[/math]: program string p(string y): string V(string x, string y): ... string main(): return V(getSrc(), y) string getSrc(): string src = getOtherSrc() return "$src string getOtherSrc():\n return src\n" string getOtherSrc(): return "function p(int y): int V(string x, int y): ... int main(): return V(getSrc(), y) string getSrc(): string src = getOtherSrc() return \"$src string getOtherSrc():\n return src\n\"

[math]\triangleleft[/math]

Иначе говоря, если рассмотреть [math]V(x, y)[/math], как программу, использующую [math]x[/math] в качестве исходного кода и выполняющую действие над [math]y[/math], то теорема о рекурсии показывает, что мы можем написать эквивалентную ей программу [math]p(y) = V(p, y)[/math], которая будет использовать собственный исходный код.

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

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

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

Определение:

Функция [math]g[/math] называется [math]\equiv[/math] — продолжением ([math]\equiv[/math] — continuation) функции [math]f[/math], если для всех таких [math]x[/math], что [math]f(x)[/math] определено, [math]g(x) \equiv f(x)[/math].

Лемма:

Для всякой вычислимой функции [math]f[/math] существует вычислимая и всюду определенная функция [math]g[/math], являющаяся ее [math]\equiv[/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] \exists n : W_n = \{n\} [/math], где [math] W_n [/math] — множество слов, допускаемых программой с номером [math] n [/math].

[math]\triangleright[/math]

По теореме о рекурсии, программа может знать свой исходный код. Значит, в неё можно написать функцию [math] \mathrm{getSrc()} [/math], которая вернёт строку — исходный код программы. Напишем такую программу: [math]p(q){:}[/math] if [math]p. \mathrm{getSrc()}[/math] == [math]q. \mathrm{getSrc()}[/math] return 1 else while true Программа [math] p [/math] знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число — свой номер.

[math]\triangleleft[/math]

Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка

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

Лемма:

Язык [math]L=\{p \mid p(\varepsilon)=\perp\}[/math] неразрешим.

Доказательство:

[math]\triangleright[/math]

Предположим обратное, тогда существует программа [math]r[/math] разрещающая [math]L[/math]. Рассмотрим следущую программу: [math]p(x){:}[/math] if [math]r(\mathrm{getSrc()})[/math] 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]

См. также

• Участник:Shersh/Теорема_о_рекурсии

Источники информации

• Wikipedia — Kleene's recursion theorem
• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 - С. 176
• Kleene, Stephen On notation for ordinal numbers - The Journal of Symbolic Logic, 1938 - С. 150-155