Теорема Клина о рекурсии - Kleenes recursion theorem - Wikipedia

Не путать с Теорема Клини для обычных языков.

В теория вычислимости, Клини рекурсивные теоремы представляют собой пару фундаментальных результатов о применении вычислимые функции к их собственным описаниям. Впервые теоремы были доказаны Стивен Клини в 1938 году и появляется в его книге 1952 года Введение в метаматематику. Связанная теорема, которая строит неподвижные точки вычислимой функции, известна как Теорема Роджерса и это связано с Хартли Роджерс младший (Роджерс 1967 ).

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

Обозначение

Формулировка теорем относится к допустимая нумерация ${\displaystyle \varphi }$ из частичные рекурсивные функции, такая, что функция, соответствующая индексу ${\displaystyle e}$ является ${\displaystyle \varphi _{e}}$. С точки зрения программирования, ${\displaystyle e}$ представляет собой программу и ${\displaystyle \varphi _{e}}$ представляет функцию, вычисленную этой программой.

Если ${\displaystyle F}$ и ${\displaystyle G}$ находятся частичные функции на натуральных числах обозначение ${\displaystyle F\simeq G}$ указывает, что для каждого п, либо ${\displaystyle F(n)}$ и ${\displaystyle G(n)}$ оба определены и равны, иначе ${\displaystyle F(n)}$ и ${\displaystyle G(n)}$ оба не определены.

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

Учитывая функцию ${\displaystyle F}$, а фиксированная точка из ${\displaystyle F}$ это индекс ${\displaystyle e}$ такой, что ${\displaystyle \varphi _{e}\simeq \varphi _{F(e)}}$. Роджерс (Роджерс 1967, §11.2) описывает следующий результат как «более простую версию» (второй) теоремы Клини о рекурсии.

Теорема Роджерса о неподвижной точке. Если ${\displaystyle F}$ является тотально вычислимой функцией, у нее есть фиксированная точка.

Доказательство теоремы о неподвижной точке

В доказательстве используется конкретная полная вычислимая функция ${\displaystyle h}$, определяемый следующим образом. Учитывая натуральное число ${\displaystyle x}$, функция ${\displaystyle h}$ выводит индекс частично вычислимой функции, которая выполняет следующие вычисления:

Учитывая ввод ${\displaystyle y}$, первая попытка вычислить ${\displaystyle \varphi _{x}(x)}$. Если это вычисление возвращает результат ${\displaystyle e}$, затем вычислить ${\displaystyle \varphi _{e}(y)}$ и вернуть его значение, если оно есть.

Таким образом, для всех показателей ${\displaystyle x}$ частичных вычислимых функций, если ${\displaystyle \varphi _{x}(x)}$ определено, то ${\displaystyle \varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}}$. Если ${\displaystyle \varphi _{x}(x)}$ не определено, то ${\displaystyle \varphi _{h(x)}}$ это функция, которая нигде не определена. Функция ${\displaystyle h}$ может быть построена из частично вычислимой функции ${\displaystyle g(x,y)}$ описанный выше и s-m-n теорема: для каждого ${\displaystyle x}$, ${\displaystyle h(x)}$ это индекс программы, которая вычисляет функцию ${\displaystyle y\mapsto g(x,y)}$.

Для завершения доказательства пусть ${\displaystyle F}$ - любая полная вычислимая функция, и построить ${\displaystyle h}$ как указано выше. Позволять ${\displaystyle e}$ быть индексом композиции ${\displaystyle F\circ h}$, которая является полной вычислимой функцией. потом ${\displaystyle \varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}}$ по определению ${\displaystyle h}$.Но потому что ${\displaystyle e}$ это индекс ${\displaystyle F\circ h}$, ${\displaystyle \varphi _{e}(e)=(F\circ h)(e)}$, и поэтому ${\displaystyle \varphi _{\varphi _{e}(e)}\simeq \varphi _{F(h(e))}}$. По транзитивности ${\displaystyle \simeq }$, это означает ${\displaystyle \varphi _{h(e)}\simeq \varphi _{F(h(e))}}$. Следовательно ${\displaystyle \varphi _{n}\simeq \varphi _{F(n)}}$ за ${\displaystyle n=h(e)}$.

Это доказательство является конструкцией частичная рекурсивная функция который реализует Y комбинатор.

Функции без фиксированной точки

Функция ${\displaystyle F}$ такой, что ${\displaystyle \varphi _{e}\not \simeq \varphi _{F(e)}}$ для всех ${\displaystyle e}$ называется без фиксированной точки. Теорема о неподвижной точке показывает, что никакая полная вычислимая функция не свободна от неподвижной точки, но есть много невычислимых функций без неподвижной точки. Критерий полноты Арсланова заявляет, что единственный рекурсивно перечислимый Степень Тьюринга который вычисляет функцию без фиксированной точки, 0′, степень проблема остановки (Soare 1987, п. 88).

Вторая теорема о рекурсии Клини

Вторая теорема о рекурсии - это обобщение теоремы Роджерса со вторым входом в функцию. Одна неформальная интерпретация второй теоремы о рекурсии состоит в том, что можно строить самореференциальные программы; см. «Применение к лугам» ниже.

Вторая теорема о рекурсии. Для любой частично рекурсивной функции ${\displaystyle Q(x,y)}$ есть указатель ${\displaystyle p}$ такой, что ${\displaystyle \varphi _{p}\simeq \lambda y.Q(p,y)}$.

Теорема может быть доказана из теоремы Роджерса, если положить ${\displaystyle F(p)}$ - функция такая, что ${\displaystyle \varphi _{F(p)}(y)=Q(p,y)}$ (конструкция, описанная S-m-n теорема ). Затем можно проверить, что неподвижная точка этого ${\displaystyle F}$ это индекс ${\displaystyle p}$ как требуется. Теорема конструктивна в том смысле, что фиксированная вычислимая функция отображает индекс для Q в индекс п.

Сравнение с теоремой Роджерса

Вторую теорему о рекурсии Клини и теорему Роджерса можно довольно просто доказать друг из друга (Джонс 1997 С. 229–230). Однако прямое доказательство теоремы Клини (Клини 1952, pp. 352–353) не использует универсальную программу, а это означает, что теорема верна для некоторых систем субрекурсивного программирования, которые не имеют универсальной программы.

Применение к лугам

Классическим примером использования второй теоремы о рекурсии является функция ${\displaystyle Q(x,y)=x}$. Соответствующий индекс ${\displaystyle p}$ в этом случае дает вычислимую функцию, которая выводит собственный индекс при применении к любому значению (Катленд 1980, п. 204). Выраженные в виде компьютерных программ, такие индексы известны как Quines.

Следующий пример в Лисп показывает, как ${\displaystyle p}$ в следствии может быть эффективно получено из функции ${\displaystyle Q}$. Функция s11 в коде есть функция этого имени, созданная S-m-n теорема.

Q можно заменить на любую функцию с двумя аргументами.

(setq Q '(лямбда (Икс у) Икс))(setq s11 '(лямбда (ж Икс) (список лямбда '(у) (список ж Икс 'у))))(setq п (список лямбда '(Икс у) (список Q (список s11 'Икс 'Икс) 'у)))(setq п (оценка (список s11 п п)))

Результаты следующих выражений должны быть такими же. ${\displaystyle \varphi }$ p (ноль)

(оценка (список п ноль))

Q (p, ноль)

(оценка (список Q п ноль))

Приложение для устранения рекурсии

Предположим, что ${\displaystyle g}$ и ${\displaystyle h}$ - это общие вычислимые функции, которые используются в рекурсивном определении функции ${\displaystyle f}$:

${\displaystyle f(0,y)\simeq g(y),}$

${\displaystyle f(x+1,y)\simeq h(f(x,y),x,y),}$

Вторую теорему о рекурсии можно использовать, чтобы показать, что такие уравнения определяют вычислимую функцию, где понятие вычислимости не должно допускать, на первый взгляд, рекурсивных определений (например, оно может быть определено следующим образом: μ-рекурсия, или Машины Тьюринга ). Это рекурсивное определение можно преобразовать в вычислимую функцию ${\displaystyle \varphi _{F}(e,x,y)}$ это предполагает ${\displaystyle e}$ является индексом самого себя для имитации рекурсии:

${\displaystyle \varphi _{F}(e,0,y)\simeq g(y),}$

${\displaystyle \varphi _{F}(e,x+1,y)\simeq h(\varphi _{e}(x,y),x,y).}$

Теорема о рекурсии устанавливает существование вычислимой функции ${\displaystyle \varphi _{f}}$ такой, что ${\displaystyle \varphi _{f}(x,y)\simeq \varphi _{F}(f,x,y)}$. Таким образом ${\displaystyle f}$ удовлетворяет данному рекурсивному определению.

Рефлексивное программирование

Рефлексивный, или отражающий, программирование относится к использованию ссылок на самих себя в программах. Джонс (Джонс 1997 ) представляет собой взгляд на вторую теорему рекурсии на основе рефлексивного языка. Показано, что определенный рефлексивный язык не сильнее языка без рефлексии (поскольку интерпретатор рефлексивного языка может быть реализован без использования рефлексии); затем показано, что теорема о рекурсии почти тривиальна на рефлексивном языке.

Первая теорема о рекурсии

В то время как вторая теорема о рекурсии касается неподвижных точек вычислимых функций, первая теорема о рекурсии связана с неподвижными точками, определяемыми операторами перечисления, которые являются вычислимым аналогом индуктивных определений. An оператор перечисления набор пар (А,п) куда А это (код для а) конечного набора чисел и п одно натуральное число. Часто, п будет рассматриваться как код для упорядоченной пары натуральных чисел, особенно когда функции определены с помощью операторов перечисления. Операторы перечисления имеют центральное значение при изучении сводимость перечисления.

Каждый оператор перечисления Φ определяет функцию от наборов натуральных чисел до наборов натуральных чисел, заданных формулой

${\displaystyle \Phi (X)=\{n\mid \exists A\subseteq X[(A,n)\in \Phi ]\}.}$

А рекурсивный оператор - это оператор перечисления, который при задании графика частично рекурсивной функции всегда возвращает график частично рекурсивной функции.

Неподвижной точкой оператора перечисления Φ называется множество F такое, что Φ (F) = F. Первая теорема перечисления показывает, что неподвижные точки могут быть эффективно получены, если сам оператор перечисления вычислим.

Первая теорема рекурсии. Имеют место следующие утверждения.

1. Для любого вычислимого оператора перечисления Φ существует рекурсивно перечислимое множество F такое, что Φ (F) = F и F наименьший набор с этим свойством.
2. Для любого рекурсивного оператора существует частично вычислимая функция φ такая, что (φ) = φ и φ - наименьшая частично вычислимая функция с этим свойством.

Пример

Как и вторая теорема о рекурсии, первая теорема о рекурсии может использоваться для получения функций, удовлетворяющих системам рекурсивных уравнений. Чтобы применить первую теорему рекурсии, уравнения рекурсии должны быть сначала преобразованы в рекурсивный оператор.

Рассмотрим рекурсивные уравнения для факториал функция ж:

${\displaystyle f(0)=1}$

${\displaystyle f(n+1)=(n+1)\cdot f(n)}$

Соответствующий рекурсивный оператор Φ будет иметь информацию, которая сообщает, как перейти к следующему значению ж от предыдущего значения. Однако рекурсивный оператор фактически определяет график ж. Во-первых, Φ будет содержать пару ${\displaystyle (\varnothing ,(0,1))}$. Это указывает на то, что ж(0) однозначно 1, и, следовательно, пара (0,1) находится в графике ж.

Далее для каждого п и м, Φ будет содержать пару ${\displaystyle (\{(n,m)\},(n+1,(n+1)\cdot m))}$. Это означает, что если ж(п) является м, тогда ж(п + 1) равно (п + 1)м, так что пара (п + 1, (п + 1)м) находится в графике ж. В отличие от базового случая ж(0) = 1, рекурсивный оператор требует некоторой информации о ж(п) до того, как он определит значение ж(п + 1).

Первая теорема о рекурсии (в частности, часть 1) утверждает, что существует множество F такое, что Φ (F) = F. Множество F будет полностью состоять из упорядоченных пар натуральных чисел и будет графиком факториальной функции ж, по желанию.

Ограничение рекурсивных уравнений, которые могут быть преобразованы в рекурсивные операторы, гарантирует, что рекурсивные уравнения действительно определяют наименьшую фиксированную точку. Например, рассмотрим систему рекурсионных уравнений:

${\displaystyle g(0)=1}$

${\displaystyle g(n+1)=1}$

${\displaystyle g(2n)=0}$

Нет функции грамм удовлетворяющие этим уравнениям, поскольку из них следует грамм(2) = 1, а также следует грамм(2) = 0. Таким образом, неподвижной точки нет. грамм удовлетворяющие этим рекурсивным уравнениям. Можно сделать оператор перечисления, соответствующий этим уравнениям, но он не будет рекурсивным оператором.

Схема доказательства первой теоремы о рекурсии

Доказательство части 1 первой теоремы о рекурсии получается повторением оператора перечисления Φ, начиная с пустого множества. Сначала последовательность F_k построен, для ${\displaystyle k=0,1,\ldots }$. Позволять F₀ быть пустым множеством. Действуя индуктивно, для каждого k, позволять F_{k + 1} быть ${\displaystyle F_{k}\cup \Phi (F_{k})}$. Ну наконец то, F считается ${\displaystyle \bigcup F_{k}}$. Остальная часть доказательства состоит из проверки того, что F рекурсивно перечислимо и является наименьшей неподвижной точкой Φ. Последовательность F_k в этом доказательстве соответствует цепи Клини в доказательстве Теорема Клини о неподвижной точке.

Вторая часть первой теоремы о рекурсии следует из первой части. Предположение, что Φ - рекурсивный оператор, используется, чтобы показать, что неподвижная точка Φ является графиком частичной функции. Ключевым моментом является то, что если фиксированная точка F не является графиком функции, то есть некоторые k такой, что F_k не является графиком функции.

Сравнение со второй теоремой о рекурсии

По сравнению со второй теоремой о рекурсии, первая теорема о рекурсии дает более сильный вывод, но только тогда, когда удовлетворяются более узкие гипотезы. Роджерс (Роджерс 1967 ) использует термин слабая теорема рекурсии для первой теоремы о рекурсии и сильная теорема рекурсии для второй теоремы о рекурсии.

Одно различие между первой и второй теоремами рекурсии состоит в том, что неподвижные точки, полученные с помощью первой теоремы рекурсии, гарантированно будут наименьшими неподвижными точками, в то время как точки, полученные из второй теоремы рекурсии, могут не быть наименьшими неподвижными точками.

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

Обобщенная теорема

В контексте его теории нумерации Ершов показал, что теорема Клини верна для любого предполная нумерация (Барендрегт и Тервейн 2019, п. 1151). Гёделевская нумерация - это предполная нумерация на множестве вычислимых функций, поэтому обобщенная теорема дает теорему о рекурсии Клини как частный случай. Видеть (Ершов 1999, §4.14) для обзора на английском языке.

Учитывая предполную нумерацию ${\displaystyle \nu }$ тогда для любой частично вычислимой функции ${\displaystyle f}$ с двумя параметрами существует полная вычислимая функция ${\displaystyle t}$ с одним параметром таким, что

${\displaystyle \forall n\in \mathbb {N} :\nu \circ f(n,t(n))=\nu \circ t(n).}$

Смотрите также

• Денотационная семантика, где другая теорема о наименьшей неподвижной точке используется с той же целью, что и первая теорема о рекурсии.
• Комбинаторы с фиксированной точкой, которые используются в лямбда-исчисление с той же целью, что и первая теорема о рекурсии.

Рекомендации

• Барендрегт, Хенк; Тервейн, Себастьян А. (2019). «Теоремы о неподвижной точке для предполных нумераций». Анналы чистой и прикладной логики. 170 (10): 1151–1161. Дои:10.1016 / j.apal.2019.04.013. HDL:2066/205967. ISSN  0168-0072. Получено 6 мая 2020.
• Катленд, Найджел Дж. (1980). Вычислимость: введение в теорию рекурсивных функций. Издательство Кембриджского университета. Дои:10.1017 / cbo9781139171496. ISBN  9781139935609. OCLC  488175597. Получено 6 мая 2020.
• Ершов Юрий Л (1999). «Часть 4: Математика и теория вычислимости. 14. Теория нумерации». В Гриффоре, Эдвард Р. (ред.). Справочник по теории вычислимости. Исследования по логике и основам математики. 140. Амстердам: Эльзевир. С. 473–503. ISBN  9780444898821. OCLC  162130533. Получено 6 мая 2020.
• Клини, С. (1938). «Об обозначениях порядковых чисел» (PDF). Журнал символической логики. 3 (4): 150–155. Дои:10.2307/2267778. ISSN  0022-4812. JSTOR  2267778. Получено 6 мая 2020.
• Клини, С. (1952). Введение в метаматематику. Bibliotheca Mathematica. Издательство Северной Голландии. ISBN  9780720421033. OCLC  459805591. Получено 6 мая 2020.
• Jockusch, C.G.; Лерман, М .; Соаре, Р.И.; Соловей, Р.М. (1989). «Рекурсивно перечислимые множества по модулю повторных скачков и расширения критерия полноты Арсланова». Журнал символической логики. 54 (4): 1288–1323. Дои:10.1017 / S0022481200041104. ISSN  0022-4812. JSTOR  2274816.
• Джонс, Нил Д. (1997). Вычислимость и сложность: с точки зрения программирования. Кембридж, Массачусетс: MIT Press. ISBN  9780262100649. OCLC  981293265.
• Роджерс, Хартли (1967). Теория рекурсивных функций и эффективная вычислимость. Кембридж, Массачусетс: MIT Press. ISBN  9780262680523. OCLC  933975989. Получено 6 мая 2020.
• Соаре, Р.И. (1987). Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо генерируемых множеств. Перспективы математической логики. Берлин; Нью-Йорк: Springer-Verlag. ISBN  9780387152998. OCLC  318368332.

внешняя ссылка

• «Рекурсивные функции» запись Пьерджиоргио Одифредди в Стэнфордская энциклопедия философии, 2012.