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

Материал из Циклопедии
Перейти к навигации Перейти к поиску

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

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

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

Формулировка[править]

Первая теорема о рекурсии[править]

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

При каждом справедливо следующее утверждение. Пусть — частично-рекурсивный оператор, в котором функциональная переменная пробегает частичные функции от переменных. Тогда функциональное уравнение имеет для такое решение , что всякое решение для служит продолжением функции , и это решение — частично-рекурсивно. Аналогично, если состоит из частичных функций и предикатов, то имеет для такое решение , что всякое решение для служит продолжением функции , и это решение — частично-рекурсивно относительно .

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

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

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

Пусть — рекурсивная функция. Тогда имеет наименьшую неподвижную точку , которая вычислима:

1)

2) такой, что ,где

3) также вычислима.

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

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

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

Вторая теорема о рекурсии[править]

Для любой частично рекурсивной функции существует индекс такой, что .

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

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

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

Обобщённая теорема[править]

Теорема Клини о рекурсии была обобщена на предполные нумерации Юрием Ершовым[2]. Используя терминологию Ершова, результат Клини формулируется следующим образом: h имеет неподвижную точку по модулю , где γ — нумерация функций ПК. Учитывая предварительную полную нумерацию, то для любой частично вычислимой функции с двумя параметрами существует полная вычислимая функция с одним параметром таким, что:

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

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

Примеры[править]

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


Рассмотрим уравнения рекурсии для факториальной функции f :

Соответствующий рекурсивный оператор Φ будет иметь информацию, которая сообщает, как добраться до следующего значения f из предыдущего значения. Однако рекурсивный оператор фактически определит график f . Во-первых, Φ будет содержать пару. Это означает, что f (0) однозначно равно 1, и, таким образом, пара (0,1) находится в графике f . Далее, для каждого n и m , Φ будет содержать пару . Это означает, что если f ( n ) равно m , то f ( n + 1) равно ( n + 1) m , так что пара ( n + 1, ( n + 1) m ) находится в графике f . В отличие от базового случая f (0) = 1 , рекурсивный оператор требует некоторой информации о f ( n ) , прежде чем он определит значение f ( n + 1) .

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

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

Примечания[править]

  1. Стефен К. Клини Введение в метаматематику / Успенский В.А.. — М.: Иностранная литература, 1957. — С. 310-317. — 524 с.
  2. Ершов Ю.Л. Теория нумераций. — М.: Наука, 1977. — 416 с.

Литература[править]

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

Ссылки[править]

Рувики

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Теорема Клини о рекурсии», расположенная по адресу:

Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий.

Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».