693
правки
Изменения
→Теорема о рекурсии
==Теорема о рекурсии==
Рассмотрим произвольную вычислимую функцию от двух аргументов — <tex>V(x, y)</tex>. Теорема о рекурсии утверждает, что всегда можно найти эквивалентную ей <tex>p(y) = V(p, y)</tex>, которая будет использовать саму себя для вычисления значения. Сформулируем теорему более формально.
{{Теорема
...
Тогда вызов <tex>\mathrm{p(x)}</tex> — вызов функции <tex>\ mathrm{main}</tex> от соответствующего аргумента.
Все входные данные далее можно интерпретировать как строки, поэтому все типы аргументов и возвращаемых значений будут иметь тип '''string'''. Пусть есть вычислимая <tex>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. <br> Предположим, что у нас в распоряжении есть функция <tex>\mathrm{getSrc()}</tex>, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
'''string''' getSrc():
'''string''' src = getOtherSrc()
'''return''' ```$src <font color="green">// символ $ перед названием переменной используется для подстановки значения этой переменной в строку</font>
<nowiki>|</nowiki>string getOtherSrc(): <font color="green">// многострочные строки заключаются в ``` и используют <nowiki>|</nowiki> в качестве разделителя</font>
<nowiki>|</nowiki> return $src```
Иначе говоря, если рассмотреть <tex>V(x, y)</tex>, как программу, использующую <tex>x</tex> в качестве исходного кода и выполняющую действие над <tex>y</tex>, то теорема о рекурсии показывает, что мы можем написать эквивалентную ей программу <tex>p(y) = V(p, y)</tex>, которая будет использовать собственный исходный код.
Приведем так же альтернативую альтернативную формулировку теоремы и альтернативное (неконструктивное) доказательство.
==Теорема о неподвижной точке==
По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы.
Напишем такую программу:
<tex>p(q){:}</tex>
'''if''' <tex>p. \mathrm{getSrc()}</tex> == <tex>q. \mathrm{getSrc()}</tex>
'''return''' 1
'''else'''
'''while''' ''true''
Программа <tex> p </tex> знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число {{---}} свой номер.
}}
==Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка==
Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex>.
{{Лемма
|statement= Язык <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex> неразрешим.
|proof=
Предположим обратное, тогда . Тогда существует программа <tex>r</tex> разрещающая , разрешающая <tex>L</tex>.Рассмотрим следущую следующую программу:<code> <tex> p(x){:}</tex> '''if''' <tex>r(\mathrm{getSrc()})</tex> '''return''' 1 '''while''' ''true''</code>Пусть <tex>p(\epsilonvarepsilon)=\perp</tex>. Тогда условие <tex>r(p)</tex> выполняется и <tex>p(\epsilonvarepsilon)=1</tex>. Противоречие. Если <tex>p(\epsilonvarepsilon) \ne \perp</tex>, то <tex>r(p)</tex> не выполняется и <tex>p(\epsilonvarepsilon)=\perp</tex>. Противоречие.
}}
