Теорема Клини о рекурсии

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

Теоремы были впервые доказаны Стивеном Клини в 1938 году.

Существует также Теорема Клини для регулярных языков.

Формулировка

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

Формулировка даётся по книге С. Клини «Введение в метаматематику», 1957 г.

При каждом Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n\geqslant0} справедливо следующее утверждение. Пусть Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle F(\xi,x_1,...,x_n)} — частично-рекурсивный оператор, в котором функциональная переменная Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \xi} пробегает частичные функции от Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} переменных. Тогда функциональное уравнение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \xi(x_1,...,x_n)\simeq F(\xi;x_1,...,x_n)} имеет для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \xi} такое решение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi} , что всякое решение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi'} для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \xi} служит продолжением функции Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi} , и это решение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi} — частично-рекурсивно. Аналогично, если Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Psi} состоит из Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle l} частичных функций и предикатов, то Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \xi(x_1,...,x_n)\simeq F(\xi;x_1,...,x_n)} имеет для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \xi} такое решение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi} , что всякое решение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi'} для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \xi} служит продолжением функции Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi} , и это решение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi} — частично-рекурсивно относительно Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Psi} .

Имеют место следующие утверждения:

1. Для любого вычислимого оператора перечисления Φ существует рекурсивно перечислимое множество F такое, что Φ( F ) = F и F является наименьшим множеством с этим свойством. Оператор перечисления представляет собой набор пар ( A , n ), где A — это ( код для a) конечного множества чисел, а n — одно натуральное число. Часто n будет рассматриваться как код для упорядоченной пары натуральных чисел, особенно когда функции определяются с помощью операторов перечисления. Операторы перечисления имеют центральное значение в изучении сводимости перечисления .
2. Рекурсивный оператор — это оператор перечисления, который при задании графика частично рекурсивной функции всегда возвращает график частично рекурсивной функции. Операторы перечисления имеют центральное значение в изучении сводимости перечисления. Каждый оператор перечисления Φ определяет функцию из множеств натуральных чисел в множества натуральных чисел, заданные формулой:

   Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Phi(X) = \{ n \mid \exists A \subseteq X [(A,n) \in \Phi]\}.}

Существует также определение, которое можно применить к рекурсивным функциям следующим образом:

Пусть Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Phi: \mathbb{F}(\mathbb{N}^k) \rightarrow (\mathbb{N}^k)} — рекурсивная функция. Тогда Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Phi} имеет наименьшую неподвижную точку Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f_{\Phi}: \mathbb{N}^k \rightarrow \mathbb{N}} , которая вычислима:

1) Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Phi(f_{\phi})=f_{\Phi}}

2) Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \forall g \in \mathbb{F}(\mathbb{N}^k)} такой, что Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Phi(g)=g} ,где Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f_{\Phi}\subseteq g}

3) Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f_{\Phi}} также вычислима.

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

Утверждение теорем относится к допустимой нумерации Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi} частично рекурсивных функций , таких, что функция, соответствующая индексу Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle e} является Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi_e} .

Неподвижная точка оператора перечисления Φ — это множество F, такое что Φ( F ) = F. Первая теорема перечисления показывает, что неподвижные точки могут быть эффективно получены, если сам оператор перечисления вычислим. Если Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle F} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G} являются частичными функциями от натуральных чисел, выражение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle F \simeq G} обозначает, что для каждого n , либо Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle F(n)} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G(n)} оба определены и равны, иначе Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle F(n)} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G(n)} оба не определены.

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

Для любой частично рекурсивной функции Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle Q(x,y)} существует индекс Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p} такой, что Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi_p \simeq \lambda y.Q(p,y)} .

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

Эта теорема утверждает, что для любой вычислимой функции V(n,x) существует эквивалентная вычислимая функция p(y)=V(p,y), которая использует саму себя для вычисления значения.

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

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

Теорема Клини о рекурсии была обобщена на предполные нумерации Юрием Ершовым. Используя терминологию Ершова, результат Клини формулируется следующим образом: h имеет неподвижную точку по модулю , где γ — нумерация функций ПК. Учитывая предварительную полную нумерацию, то для любой частично вычислимой функции Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \nu} с двумя параметрами существует полная вычислимая функция Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f} с одним параметром Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle t} таким, что:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \forall n \in \mathbb{N} : \nu \circ f(n,t(n)) = \nu \circ t(n).}

Работы Ершова Ю.Л, по теории рекурсии на допустимых множествах стали основой для разработки новой концепции программирования — семантического программирования.

Теорема рекурсии была обобщена другими способами Виссером и Арслановым. Виссер доказал так называемую «теорему антидиагональной нормализации». Арсланов распространил теорему рекурсии с вычислимых функций на произвольные функции, вычислимые из неполной перечислимой степени Тьюринга.

Примеры

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

Рассмотрим уравнения рекурсии для факториальной функции f :Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(0) = 1; f(n+1)=(n + 1)\cdot f(n)} Соответствующий рекурсивный оператор Φ будет иметь информацию, которая сообщает, как добраться до следующего значения f из предыдущего значения. Однако рекурсивный оператор фактически определит график f . Во-первых, Φ будет содержать пару. Это означает, что f (0) однозначно равно 1, и, таким образом, пара (0,1) находится в графике f . Далее, для каждого n и m , Φ будет содержать пару Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle ( \{ (n, m) \}, (n+1, (n+1)\cdot m))} . Это означает, что если f ( n ) равно m , то f ( n + 1) равно ( n + 1) m , так что пара ( n + 1, ( n + 1) m ) находится в графике f . В отличие от базового случая f (0) = 1 , рекурсивный оператор требует некоторой информации о f ( n ) , прежде чем он определит значение f ( n + 1) .

Ограничение на уравнения рекурсии, которые могут быть преобразованы в рекурсивные операторы, гарантирует, что уравнения рекурсии фактически определяют наименьшую фиксированную точку. Например, рассмотрим набор уравнений рекурсии:Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{align} &g(0) = 1\\ &g(n + 1) = 1\\ &g(2n) = 0 \end{align}} Не существует функции g, удовлетворяющей этим уравнениям, поскольку они подразумевают g (2) = 1, а также подразумевают g (2) = 0. Таким образом, не существует неподвижной точки g, удовлетворяющей этим уравнениям рекурсии. Можно создать оператор перечисления, соответствующий этим уравнениям, но он не будет рекурсивным оператором.

Литература

• Ершов Ю.Л. Теория нумераций. — М.: Наука, 1977. — 416 с.

Ссылки

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Теорема Клини о рекурсии», расположенная по адресу: — https://ru.ruwiki.ru/wiki/Теорема_Клини_о_рекурсии Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».