Теорема о рекурсии — различия между версиями
Arimon (обсуждение | вклад) м (→Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка) |
м (→Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка) |
||
Строка 125: | Строка 125: | ||
}} | }} | ||
− | ==Пример использования теоремы о рекурсии в доказательстве | + | ==Пример использования теоремы о рекурсии в доказательстве неразрешимости языка== |
Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex>. | Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex>. | ||
{{Лемма | {{Лемма | ||
Строка 131: | Строка 131: | ||
|statement= Язык <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex> неразрешим. | |statement= Язык <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex> неразрешим. | ||
|proof= | |proof= | ||
− | Предположим обратное | + | Предположим обратное. Тогда существует программа <tex>r</tex>, разрешающая <tex>L</tex>. |
− | Рассмотрим | + | Рассмотрим следующую программу: |
<code> | <code> | ||
<tex>p(x){:}</tex> | <tex>p(x){:}</tex> |
Версия 01:46, 8 мая 2020
Содержание
Теорема о рекурсии
Рассмотрим произвольную вычислимую функцию от двух аргументов —
. Теорема о рекурсии утверждает, что всегда можно найти эквивалентную ей , которая будет использовать саму себя для вычисления значения. Сформулируем теорему более формально.Теорема (Клини, о рекурсии / Kleene's recursion theorem): |
Пусть вычислимая функция. Тогда найдётся такая вычислимая , что . — |
Доказательство: |
Приведем конструктивное доказательство теоремы. Введем новые обозначения для псевдокода. Внутри блока program располагаются функции, среди которых есть функция :program int p(int x): ... int main(): ... ... Тогда вызов — вызов функции от соответствующего аргумента.Все входные данные далее можно интерпретировать как строки, поэтому все типы аргументов и возвращаемых значений будут иметь тип string. Пусть есть вычислимая program string p(string y): string V(string x, string y): ... string main(): return V(getSrc(), y) string getSrc(): ... Теперь нужно определить функцию . Предположим, что внутри мы можем определить функцию , состоящую из одного оператора , которая вернет весь предшествующий ей код. Тогда перепишется так.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(): ... Теперь 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\``` |
Иначе говоря, если рассмотреть
, как программу, использующую в качестве исходного кода и выполняющую действие над , то теорема о рекурсии показывает, что мы можем написать эквивалентную ей программу , которая будет использовать собственный исходный код.Приведем так же альтернативую формулировку теоремы и альтернативное (неконструктивное) доказательство.
Теорема о неподвижной точке
Введем на множестве натуральных чисел следующее отношение:
и докажем вспомогательную лемму.Определение: |
Функция | называется — продолжением ( — continuation) функции , если для всех таких , что определено, .
Лемма: |
Для всякой вычислимой функции существует вычислимая и всюду определенная функция , являющаяся ее — продолжением. |
Доказательство: |
Рассмотрим вычислимую функцию от двух аргументов . Так как — вычислимая, то существует вычислимая и всюду определенная функция такая, что: .Покажем, что Таким образом, мы нашли будет являться — продолжением функции . Если определено, то вернет другой номер той же вычислимой функции. Если же не определено, то вернет номер нигде не определенной функции. — продолжение для произвольно взятой вычислимой функции . |
Теорема (Роджерс, о неподвижной точке / Rogers' fixed-point theorem): |
Пусть универсальная функция для класса вычислимых функций одного аргумента, — всюду определённая вычислимая функция одного аргумента. Тогда найдется такое , что , то есть и — номера одной функции. — |
Доказательство: |
Будем доказывать теорему от противного: предположим, что существует всюду определенная вычислимая функция , такая, что для любого . В терминах введенного нами отношения, это значит, что не имеет — неподвижных точек.Рассмотрим некоторую вычислимую функцию, от которой никакая вычислимая функция не может отличаться всюду. Такой будет, например Согласно доказанной нами лемме, существует вычислимая и всюду определенная функция (действительно, если предположить, что существует вычислимая функция , всюду отличная от , то нарушается определение универсальной функции.) , являющаяся — продолжением функции . Давайте зададим функцию следующим образом: , где — искомая всюду определенная, вычислимая функция, не имеющая — неподвижных точек. Тогда всюду отличается от (в силу того, что не имеет неподвижных точек.) Получили противоречие, из чего следует, что такой функции не существует. |
Утверждение: |
, где — множество слов, допускаемых программой с номером . |
По теореме о рекурсии, программа может знать свой исходный код. Значит, в неё можно написать функцию , которая вернёт строку — исходный код программы.
Напишем такую программу:
if == return 1 else while true Программа знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число — свой номер. |
Пример использования теоремы о рекурсии в доказательстве неразрешимости языка
Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка
.Лемма: |
Язык неразрешим. |
Доказательство: |
Предположим обратное. Тогда существует программа
if r(getSrc())
return 1
while true
Пусть . Тогда условие выполняется и . Противоречие. Если , то не выполняется и . Противоречие. |
См. также
Источники информации
- Wikipedia — Kleene's recursion theorem
- Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 - С. 176
- Kleene, Stephen On notation for ordinal numbers - The Journal of Symbolic Logic, 1938 - С. 150-155