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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о неподвижной точке)
м (rollbackEdits.php mass rollback)
 
(не показано 66 промежуточных версий 18 участников)
Строка 1: Строка 1:
==Теорема о рекурсии==
+
==Теорема о рекурсии==  
  
 +
Рассмотрим произвольную вычислимую функцию от двух аргументов — <tex>V(x, y)</tex>. Теорема о рекурсии утверждает, что всегда можно найти эквивалентную ей <tex>p(y) = V(p, y)</tex>, которая будет использовать саму себя для вычисления значения. Сформулируем теорему более формально.
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
 
|author=Клини
 
|author=Клини
 
|about=о рекурсии / ''Kleene's recursion theorem''
 
|about=о рекурсии / ''Kleene's recursion theorem''
|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>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. <br> Предположим, что у нас в распоряжении есть функция <tex>getSrc()</tex>, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
 
  
<code><font size = "3em">
+
Введем новые обозначения для псевдокода. Внутри блока '''program''' располагаются функции, среди которых есть функция <tex>\mathrm{main}</tex>:
  p(y){
+
  '''program int''' p('''int''' x):
      V(x,y) {...}
+
  ...
 
   
 
   
      main() {
+
  '''int''' main():
          return V(getSrc(), y)
+
    ...
      }
 
 
    
 
    
      string getSrc() {...}
+
  ...
  }
+
Тогда вызов <tex>\mathrm{p(x)}</tex> — вызов функции <tex>\mathrm{main}</tex> от соответствующего аргумента.
</font></code>
+
 
Теперь нужно определить функцию <tex>getSrc()</tex>. Предположим, что внутри <tex>p(y)</tex> мы можем определить функцию <tex>getOtherSrc()</tex>, состоящую из одного оператора <tex>return</tex>, которая вернет весь предшествующий ей код. Тогда <tex>p(y)</tex> перепишется так.  
+
Все входные данные далее можно интерпретировать как строки, поэтому все типы аргументов и возвращаемых значений будут иметь тип '''string'''. Пусть есть вычислимая <tex>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. <br> Предположим, что у нас в распоряжении есть функция <tex>\mathrm{getSrc()}</tex>, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
<code><font size = "3em">  
+
'''program string''' p('''string''' y):
  p(y){
+
    '''string''' V('''string''' x, '''string''' y):
      V(x,y) {...}
+
      ...
 
   
 
   
      main() {
+
    '''string''' main():
          return V(getSrc(), y)
+
      '''return''' V(getSrc(), y)
      }
+
 
+
    '''string''' getSrc():
      string getSrc() {
+
      ...
          string src = getOtherSrc();
+
Теперь нужно определить функцию <tex>\mathrm{getSrc()}</tex>. Предположим, что внутри <tex>p(y)</tex> мы можем определить функцию <tex>\mathrm{getOtherSrc()}</tex>, состоящую из одного оператора <tex>\mathrm{return}</tex>, которая вернет весь предшествующий ей код. Тогда <tex>p(y)</tex> перепишется так.
          return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
 
      }
 
 
 
      string getOtherSrc() {...}
 
  }
 
</font></code>
 
  
Теперь <tex>getOtherSrc()</tex> определяется очевидным образом, и мы получаем '''итоговую версию''' функции <tex>p(y)</tex>
+
'''program string''' p('''string''' y):
<code><font size = "3em">
+
    '''string''' V('''string''' x, '''string''' y):
  p(y){
+
      ...
      V(x,y) {...}
+
 +
    '''string''' main():
 +
      '''return''' V(getSrc(), y)
 
   
 
   
      main() {
+
    '''string''' getSrc():
          return V(getSrc(), y)
+
      '''string''' src = getOtherSrc()
      }
+
      '''return''' ```$src                   <font color="green">// символ $ перед названием переменной используется для подстановки значения этой переменной в строку</font>
 
+
                <nowiki>|</nowiki>string getOtherSrc():  <font color="green">// многострочные строки заключаются в ``` и используют <nowiki>|</nowiki> в качестве разделителя</font>
      string getSrc() {
+
                <nowiki>|</nowiki>    return $src```
          string src = getOtherSrc();
 
          return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
 
      }
 
 
 
      string getOtherSrc() {
 
          return " p(y){            // Возвращаем весь предыдущий код
 
                    V(x,y) {...}
 
 
   
 
   
                      main() {
+
    '''string''' getOtherSrc():
                          return V(getSrc(), y)
+
    ...
                      }
 
 
 
                      string getSrc() {
 
                          string src = getOtherSrc();
 
                          return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
 
                  }";
 
      }
 
  }
 
</font></code>
 
  
 +
Теперь <tex>\mathrm{getOtherSrc()}</tex> определяется очевидным образом, и мы получаем '''итоговую версию''' функции <tex>p(y)</tex>:
 +
<code>
 +
'''program string''' p('''string''' y):
 +
    '''string''' V('''string''' x, '''string''' y):
 +
      ...
 +
 +
    '''string''' main():
 +
      '''return''' V(getSrc(), y)
 +
 +
    '''string''' getSrc():
 +
      '''string''' src = getOtherSrc()
 +
      '''return''' ```$src
 +
                <nowiki>|</nowiki>string getOtherSrc():
 +
                <nowiki>|</nowiki>    return $src```
 +
 +
    '''string''' getOtherSrc():
 +
      '''return''' ```function  p(int y):     
 +
                <nowiki>|</nowiki>  int V(string x, int y):
 +
                <nowiki>|</nowiki>    ...
 +
                <nowiki>|</nowiki>
 +
                <nowiki>|</nowiki>  int main():
 +
                <nowiki>|</nowiki>    return V(getSrc(), y)
 +
                <nowiki>|</nowiki>
 +
                <nowiki>|</nowiki>  string getSrc():
 +
                <nowiki>|</nowiki>    string src = getOtherSrc()
 +
                <nowiki>|</nowiki>    return \```$src
 +
                <nowiki>|</nowiki>              <nowiki>|</nowiki>string getOtherSrc():
 +
                <nowiki>|</nowiki>              <nowiki>|</nowiki>  return \$src\```
 +
</code>
 
}}
 
}}
Если говорить неформально, теорема о рекурсии утверждает, что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
+
 +
Иначе говоря, если рассмотреть <tex>V(x, y)</tex>, как программу, использующую <tex>x</tex> в качестве исходного кода и выполняющую действие над <tex>y</tex>, то теорема о рекурсии показывает, что мы можем написать эквивалентную ей программу <tex>p(y) = V(p, y)</tex>, которая будет использовать собственный исходный код.
  
Приведем так же альтернативую формулировку теоремы и альтернативное (неконструктивное) доказательство.
+
Приведем так же альтернативную формулировку теоремы и альтернативное (неконструктивное) доказательство.
  
 
==Теорема о неподвижной точке==
 
==Теорема о неподвижной точке==
 +
Введем на множестве натуральных чисел следующее отношение: <tex>x \equiv y \Leftrightarrow U_x = U_y</tex> и докажем вспомогательную лемму.
 +
{{Определение
 +
|definition = Функция <tex>g</tex> называется '''<tex>\equiv</tex> {{---}} продолжением (<tex>\equiv</tex> {{---}} continuation)''' функции <tex>f</tex>, если для всех таких <tex>x</tex>, что <tex>f(x)</tex> определено, <tex>g(x) \equiv f(x)</tex>.
 +
}}
 +
{{Лемма
 +
|statement= Для всякой вычислимой функции <tex>f</tex> существует вычислимая и всюду определенная функция <tex>g</tex>, являющаяся ее <tex>\equiv</tex> {{---}} продолжением.
 +
|proof= Рассмотрим вычислимую функцию от двух аргументов <tex> V(n, x) = U(f(n), x)</tex>. Так как <tex>V</tex> — вычислимая, то существует вычислимая и всюду определенная функция <tex>s(n)</tex> такая, что: <tex>V(n, x) = U(s(n), x)</tex>.
 +
 +
Покажем, что <tex>s(n)</tex> будет являться <tex>\equiv</tex> {{---}} продолжением функции <tex>f(n)</tex>. Если <tex>f(n)</tex> определено, то <tex>s(n)</tex> вернет другой номер той же вычислимой функции. Если же <tex>f(n)</tex> не определено, то <tex>s(n)</tex> вернет номер нигде не определенной функции.
 +
Таким образом, мы нашли <tex>\equiv</tex> {{---}} продолжение для произвольно взятой вычислимой функции <tex>f</tex>.
 +
}}
 
{{Теорема
 
{{Теорема
 
|id=th2
 
|id=th2
 
|author=Роджерс
 
|author=Роджерс
 
|about=о неподвижной точке / ''Rogers' fixed-point theorem''
 
|about=о неподвижной точке / ''Rogers' fixed-point theorem''
|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]] для класса вычислимых функций одного аргумента, <tex>h</tex> {{---}} всюду определённая [[Вычислимые_функции|вычислимая функция]] одного аргумента. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>, то есть <tex>n</tex> и <tex>h(n)</tex> - номера одной функции. Другими словами, нельзя найти алгоритма, преобразующего программы, который бы по каждой программе давал другую (не эквивалентную ей).
+
|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]] для класса вычислимых функций одного аргумента, <tex>h</tex> {{---}} всюду определённая [[Вычислимые_функции|вычислимая функция]] одного аргумента. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>, то есть <tex>n</tex> и <tex>h(n)</tex> номера одной функции.
 
|proof=
 
|proof=
Начнём с доказательства леммы.
+
Будем доказывать теорему от противного: предположим, что существует всюду определенная вычислимая функция <tex>h</tex>, такая, что <tex>U_n \neq U_{h(n)}</tex> для любого <tex>n</tex>. В терминах введенного нами отношения, это значит, что <tex>h</tex> не имеет <tex>\equiv</tex> {{---}} неподвижных точек.
{{Лемма
+
 
|statement= Пусть на натуральных числах задано отношение эквивалентности <tex>\equiv</tex>. Тогда следующие два утверждения не могут быть выполнены одновременно: <br>
+
Рассмотрим некоторую вычислимую функцию, от которой никакая вычислимая функция не может отличаться всюду. Такой будет, например <tex>f(x) = U(x, x)</tex> (действительно, если предположить, что существует вычислимая функция <tex>g(n)</tex>, всюду отличная от <tex>f(n) = U(n, n)</tex>, то нарушается определение универсальной функции.)
# Пусть <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>.
+
Согласно доказанной нами лемме, существует вычислимая и всюду определенная функция <tex>g(x)</tex>, являющаяся <tex>\equiv</tex> {{---}} продолжением функции <tex>f(x)</tex>. Давайте зададим функцию <tex>t(x)</tex> следующим образом: <tex>t(x) = h(g(x))</tex>, где <tex>h(x)</tex> — искомая всюду определенная, вычислимая функция, не имеющая <tex>\equiv</tex> {{---}} неподвижных точек. Тогда <tex>t(x)</tex> всюду отличается от <tex>f(x)</tex> (в силу того, что <tex>h(x)</tex> не имеет неподвижных точек.) Получили противоречие, из чего следует, что такой функции <tex>h</tex> не существует.
 +
}}
 +
 
 +
 
 +
{{Утверждение
 +
|id=идентификатор (необязательно), пример: proposalF.
 +
|statement = <tex> \exists n : W_n = \{n\} </tex>, где <tex> W_n </tex> {{---}} множество слов, допускаемых программой с номером <tex> n </tex>.
 
|proof=
 
|proof=
Приведем доказательство от противного. Пусть оба утверждения выполнены. <br>
+
По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы.  
Определим функцию <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>p(q){:}</tex>
Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного <tex>h</tex> <tex> \exists n</tex> такое, что <tex>U_{h(n)} = U_n</tex>.
+
    '''if''' <tex>p.\mathrm{getSrc()}</tex> == <tex>q.\mathrm{getSrc()}</tex>
 +
      '''return''' 1
 +
    '''else'''
 +
      '''while''' ''true''
 +
 
 +
Программа <tex> p </tex> знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число {{---}} свой номер.
 
}}
 
}}
  
==Пример использования==
+
==Пример использования теоремы о рекурсии в доказательстве неразрешимости языка==
Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка <tex>L=\{p|p(\epsilon)=\perp\}</tex>.
+
Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex>.
 
{{Лемма
 
{{Лемма
 
|id=st2
 
|id=st2
|statement= Язык <tex>L=\{p|p(\epsilon)=\perp\}</tex> неразрешим.  
+
|statement= Язык <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex> неразрешим.  
 
|proof=
 
|proof=
Предположим обратное, тогда существует программа <tex>r</tex> разрещающая <tex>L</tex>.
+
Предположим обратное. Тогда существует программа <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>. Противоречие.
 
}}
 
  
Доказательство [[Свойства перечислимых языков. Теорема Успенского-Райса|теоремы Успенского-Райса]] с использованием теоремы о рекурсии:
+
  p(x):
{{Теорема
+
    '''if''' r(getSrc())
|id=th3
+
      '''return''' 1
|statement=Язык никакого нетривиального свойства не является разрешимым.
+
    '''while''' ''true''
|proof=
 
Пусть <tex>F \subset RE, \varnothing \not= F \not= RE</tex>. Предположим, что язык свойства <tex>F</tex> разрешается программой <tex>d</tex>.
 
Пусть <tex>f \in L(F), g \not\in L(F)</tex>. Напишем следующую программу:
 
<code>
 
Q(x,y)
 
  if d(x)
 
    return g(y)
 
  else
 
    return f(y)
 
</code>
 
По теореме о рекурсии, <tex>\exists p \; \forall y \; p(y) = Q(p,y)</tex>.
 
  
Если <tex>p \in L(F)</tex>, то <tex>Q(p,y) = g(y) \Rightarrow p(y) = g(y) \Rightarrow p \not\in L(F)</tex>.
+
Пусть <tex>p(\varepsilon)=\perp</tex>. Тогда условие <tex>r(p)</tex> выполняется и <tex>p(\varepsilon)=1</tex>. Противоречие. Если <tex>p(\varepsilon) \ne \perp</tex>, то <tex>r(p)</tex> не выполняется и <tex>p(\varepsilon)=\perp</tex>. Противоречие.
 
+
}}
Если же <tex>p \not\in L(F)</tex>, то <tex>Q(p,y) = f(y) \Rightarrow p(y) = f(y) \Rightarrow p \in L(F)</tex>.
 
  
В обоих случаях получаем противоречие.
+
==См. также==
}}
+
*[[Участник:Shersh/Теорема_о_рекурсии]]
  
==Источники==
+
==Источники информации==
 
* [[wikipedia:Kleene's_recursion_theorem | Wikipedia {{---}} Kleene's recursion theorem]]
 
* [[wikipedia:Kleene's_recursion_theorem | Wikipedia {{---}} Kleene's recursion theorem]]
 
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999 - С. 176
 
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999 - С. 176
 
* ''Kleene, Stephen'' '''On notation for ordinal numbers''' - The Journal of Symbolic Logic, 1938 - С. 150-155
 
* ''Kleene, Stephen'' '''On notation for ordinal numbers''' - The Journal of Symbolic Logic, 1938 - С. 150-155
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]
 +
[[Категория:Разрешимые и перечислимые языки]]

Текущая версия на 19:18, 4 сентября 2022

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

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

Все входные данные далее можно интерпретировать как строки, поэтому все типы аргументов и возвращаемых значений будут иметь тип 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]\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]. Рассмотрим следующую программу:

 p(x):
   if r(getSrc())
      return 1
   while true
Пусть [math]p(\varepsilon)=\perp[/math]. Тогда условие [math]r(p)[/math] выполняется и [math]p(\varepsilon)=1[/math]. Противоречие. Если [math]p(\varepsilon) \ne \perp[/math], то [math]r(p)[/math] не выполняется и [math]p(\varepsilon)=\perp[/math]. Противоречие.
[math]\triangleleft[/math]

См. также

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

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