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

Содержание

1 Теорема о рекурсии
2 Теорема о неподвижной точке
3 Пример использования теоремы о рекурсии в доказательстве неразрешимости языка
4 См. также
5 Источники информации

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

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

Теорема (Клини, о рекурсии / Kleene's recursion theorem):

Пусть — вычислимая функция. Тогда найдётся такая вычислимая , что .

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

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

Введем новые обозначения для псевдокода. Внутри блока program располагаются функции, среди которых есть функция [math]\mathrm{main}[/math]:

program int p(int x):
  ...

  int main():
    ...
 
 ...

Тогда вызов [math]\mathrm{p(x)}[/math] — вызов функции [math]\mathrm{main}[/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```

   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(): 
               |    return $src```

   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(): 
               |              |   return \$src\```

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

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

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

Введем на множестве натуральных чисел следующее отношение: и докажем вспомогательную лемму.

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

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

Лемма:

Для всякой вычислимой функции существует вычислимая и всюду определенная функция , являющаяся ее — продолжением.

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

Рассмотрим вычислимую функцию от двух аргументов [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] вернет номер нигде не определенной функции.

Таким образом, мы нашли — продолжение для произвольно взятой вычислимой функции .

Теорема (Роджерс, о неподвижной точке / Rogers' fixed-point theorem):

Пусть — универсальная функция для класса вычислимых функций одного аргумента, — всюду определённая вычислимая функция одного аргумента. Тогда найдется такое , что , то есть и — номера одной функции.

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

Будем доказывать теорему от противного: предположим, что существует всюду определенная вычислимая функция [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] \mathrm{getSrc()} [/math], которая вернёт строку — исходный код программы. Напишем такую программу:

 [math]p(q){:}[/math]
   if [math]p.\mathrm{getSrc()}[/math] == [math]q.\mathrm{getSrc()}[/math]
     return 1
   else
     while true

Программа знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число — свой номер.

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

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

Лемма:

Язык неразрешим.

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

Предположим обратное. Тогда существует программа [math]r[/math], разрешающая [math]L[/math]. Рассмотрим следующую программу:

 p(x):
   if r(getSrc())
      return 1
   while true

Пусть . Тогда условие выполняется и . Противоречие. Если , то не выполняется и . Противоречие.

См. также

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

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

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

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

Содержание