Рекурсия курса значений

В теории вычислимости рекурсией курса значений является метод определения теоретико-числовых функций с помощью рекурсии. При определении функции f с помощью рекурсии значений, значение f (n) вычисляется из последовательности $⟨f\; (0),\; f\; (1),\dots ,\; f\; (n\; -\; 1)⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; f\; (0),\; f\; (1),\; \backslash \; ldots,\; f\; (n-1)\; \backslash \; rangle\}$.

Тот факт, что такие определения могут быть преобразованы в определения с помощью более простой формы рекурсии, часто используется для доказать, что функции, определяемые рекурсией курса значений, являются примитивно рекурсивными. В отличие от рекурсии курса значений, в примитивной рекурсии для вычисления значения функции требуется только предыдущее значение; например, для 1-арной примитивной рекурсивной функции g значение g (n + 1) вычисляется только из g (n) и n.

• 1 Определение и примеры
• 2 Эквивалентность примитивной рекурсии
• 3 Применение примитивных рекурсивных функций
• 4 Ограничения
• 5 Ссылки

Факториальная функция n! рекурсивно определяется правилами

$0!\; Знак\; равно\; 1,\; \{\backslash \; Displaystyle\; 0!\; =\; 1,\}$

$(п\; +\; 1)!\; =\; п!\; (п\; +\; 1).\; \{\backslash \; displaystyle\; (n\; +\; 1)!\; =\; n!\; (n\; +\; 1).\}$

Эта рекурсия является примитивной рекурсией, потому что она вычисляет следующее значение (n + 1)! функции на основе значения n и предыдущего значения n! функции. С другой стороны, функция Fib (n), которая возвращает n-е число Фибоначчи, определяется с помощью рекурсивных уравнений

$F\; ib\; (0)\; =\; 0,\; \{\backslash \; displaystyle\; Fib\; (0)\; =\; 0,\}$

$F\; ib\; (1)\; =\; 1,\; \{\backslash \; displaystyle\; Fib\; (1)\; =\; 1,\}$

$F\; ib\; (n\; +\; 2)\; =\; F\; ib\; (n\; +\; 1)\; +\; F\; ib\; (n).\; \{\backslash \; displaystyle\; Fib\; (n\; +\; 2)\; =\; Fib\; (n\; +\; 1)\; +\; Fib\; (n).\}$

Чтобы вычислить Fib (n + 2), требуются последние два значения функции Fib. Наконец, рассмотрим функцию g, определенную рекурсивными уравнениями

$g\; (0)\; =\; 0,\; \{\backslash \; displaystyle\; g\; (0)\; =\; 0,\}$

$g\; (n\; +\; 1)\; =\; \sum \; i\; =\; 0\; ng\; (i)\; п\; -\; я.\; \{\backslash \; displaystyle\; g\; (n\; +\; 1)\; =\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{n\}\; g\; (i)\; ^\; \{ni\}.\}$

Чтобы вычислить g (n + 1) с помощью этих уравнений, все предыдущие значения g должны быть вычислены; в общем случае для вычисления g не достаточно фиксированного конечного числа предыдущих значений. Функции Fib и g являются примерами функций, определяемых рекурсией курса значений.

В общем, функция f определяется рекурсией курса значений, если существует фиксированная примитивная рекурсивная функция h такая, что для всех n,

$f\; (n)\; =\; час\; (N,\; ⟨е\; (0),\; е\; (1),\dots ,\; е\; (п\; -\; 1)⟩)\; \{\backslash \; Displaystyle\; f\; (n)\; =\; час\; (п,\; \backslash \; langle\; f\; (0),\; f\; (1),\; \backslash \; ldots,\; f\; (n-1)\; \backslash \; rangle)\}$

где $⟨f\; (0),\; f\; (1),\dots ,\; f\; (n\; -\; 1)⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; f\; (0),\; f\; (1),\; \backslash \; ldots,\; f\; (n-1)\; \backslash \; rangle\}$- это число Гёделя, кодирующее указанную последовательность. В частности,

$f\; (0)\; =\; h\; (0,\; ⟨⟩)\; \{\backslash \; displaystyle\; f\; (0)\; =\; h\; (0,\; \backslash \; langle\; \backslash \; rangle)\}$

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

, где s [i] обозначает извлечение элемент i из закодированной последовательности s; легко заметить, что это примитивная рекурсивная функция (при условии, что используется соответствующая гёделевская нумерация).

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

$f\; (n)\; =\; h\; (n,\; ⟨f\; (0),\; f\; (1),\dots ,\; f\; (n\; -\; 1)⟩)\; \{\backslash \; displaystyle\; f\; (n)\; =\; h\; (n,\; \backslash \; langle\; f\; (0),\; f\; (1),\; \backslash \; ldots,\; f\; (n-1)\; \backslash \; rangle)\}$.

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

$f\; ¯\; (n)\; =\; ⟨f\; (0),\; f\; (1),\dots ,\; f\; (n\; -\; 1)⟩\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{f\}\}\; (n)\; =\; \backslash \; langle\; f\; (0),\; f\; (1),\; \backslash \; ldots,\; f\; (n-1)\; \backslash \; rangle\}$

где правая часть принята как нумерация Гёделя для последовательностей.

Таким образом, $f\; ¯\; (n)\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{f\}\}\; (n)\}$кодирует первые n значений f. Функция $f\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{f\}\}\}$может быть определена с помощью примитивной рекурсии, потому что $f\; ¯\; (n\; +\; 1)\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{f\}\; \}\; (n\; +\; 1)\}$получается добавлением к $f\; ¯\; (n)\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{f\}\}\; (n)\}$нового элемента $час\; (N,\; е\; ¯\; (n))\; \{\backslash \; displaystyle\; h\; (n,\; \{\backslash \; bar\; \{f\}\}\; (n))\}$:

$f\; ¯\; (0)\; =\; ⟨⟩\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{f\; \}\}\; (0)\; =\; \backslash \; langle\; \backslash \; rangle\}$,

$f\; ¯\; (n\; +\; 1)\; =\; append\; (n,\; f\; ¯\; (n),\; h\; (n,\; f\; ¯\; (n))),\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{f\}\}\; (n\; +\; 1)\; =\; \{\backslash \; mathit\; \{append\}\}\; (n,\; \{\backslash \; bar\; \{f\}\}\; (n),\; h\; (n,\; \{\backslash \; bar\; \{f\}\}\; (n))),\}$

где append (n, s, x) вычисляет, когда s кодирует последовательность длины n, новую последовательность t длины n + 1 такую, что t [n] = x и t [i] = s [i] для все я < n. This is a primitive recursive function, under the assumption of an appropriate Gödel numbering; h is assumed primitive recursive to begin with. Thus the recursion relation can be written as primitive recursion:

$е\; ¯\; (n\; +\; 1)\; =\; g\; (n,\; f\; ¯\; (n))\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{f\}\}\; (n\; +\; 1)\; =\; g\; (n,\; \{\backslash \; bar\; \{f\}\})\; (n))\}$

где g сам является примитивно рекурсивным, являясь композицией двух таких функций:

$g\; (i,\; j)\; =\; append\; (i,\; j,\; h\; (i,\; j)),\; \{\backslash \; displaystyle\; g\; (i,\; j)\; =\; \{\backslash \; mathit\; \{append\}\}\; (i,\; j,\; h\; (i,\; j)),\}$

Учитывая $f\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{f\}\}\}$, исходная функция f может быть определена как $f\; (n)\; =\; f\; ¯\; (n\; +\; 1)\; [n]\; \{\backslash \; displaystyle\; f\; (n)\; =\; \{\backslash \; bar\; \{f\}\}\; (n\; +\; 1)\; [n]\}$, что показывает, что это также примитивная рекурсивная функция.

В контексте примитивных рекурсивных функций удобно иметь средства для представления конечных последовательностей натуральных чисел как отдельных натуральных чисел. Один из таких методов, кодировка Гёделя, представляет собой последовательность положительных целых чисел $⟨n\; 0,\; n\; 1,\; n\; 2,\dots ,\; nk⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; n\_\; \{0\},\; n\_\; \{1\},\; n\_\; \{2\},\; \backslash \; ldots,\; n\_\; \{k\}\; \backslash \; rangle\}$as

$\prod \; i\; =\; 0\; kpini\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{i\; =\; 0\}\; ^\; \{k\}\; p\_\; \{i\}\; ^\; \{n\_\; \{i\}\}\}$,

где p i представляет i-е простое число. Можно показать, что в этом представлении все обычные операции над последовательностями примитивно рекурсивны. Эти операции включают в себя

• Определение длины последовательности,
• Извлечение элемента из последовательности по его индексу,
• Объединение двух последовательностей.

Используя это представление последовательностей, можно видно, что если h (m) примитивно рекурсивно, то функция

$f\; (n)\; =\; h\; (⟨f\; (0),\; f\; (1),\; f\; (2),\dots ,\; f\; (n\; -\; 1)⟩)\; \{\backslash \; displaystyle\; f\; (n)\; =\; h\; (\backslash \; langle\; f\; (0),\; f\; (1),\; f\; (2),\; \backslash \; ldots,\; f\; (n-1)\; \backslash \; rangle)\}$.

также является примитивно рекурсивным.

Когда последовательность $⟨n\; 0,\; n\; 1,\; n\; 2,\dots ,\; nk⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; n\_\; \{0\},\; n\_\; \{1\},\; n\_\; \{2\},\; \backslash \; ldots,\; n\_\; \{k\}\; \backslash \; rangle\}$может включать нули, вместо этого он представлен как

$\prod \; i\; =\; 0\; kpi\; (ni\; +\; 1)\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{i\; =\; 0\}\; ^\; \{k\; \}\; p\_\; \{i\}\; ^\; \{(n\_\; \{i\}\; +1)\}\}$,

, что позволяет различать коды для последовательностей $⟨0⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; 0\; \backslash \; rangle\}$и $⟨0,\; 0⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; 0,0\; \backslash \; rangle\}$.

Не каждое рекурсивное определение можно преобразовать в примитивное рекурсивное определение. Одним из известных примеров является функция Аккермана, которая имеет форму A (m, n) и, очевидно, не является примитивно рекурсивной.

Действительно, каждое новое значение A (m + 1, n) зависит от последовательности ранее определенных значений A (i, j), но is и js, для которых значения должны быть включены в эту последовательность, зависят сами от себя по ранее вычисленным значениям функции; а именно (i, j) = (m, A (m + 1, n)). Таким образом, нельзя закодировать ранее вычисленную последовательность значений примитивно рекурсивным способом, как было предложено выше (или вообще, как оказалось, эта функция не является примитивно рекурсивной).

• Хинман, П.Г., 2006, Основы математической логики, А. К. Петерс.
• Одифредди, П.Г., 1989, Классическая теория рекурсии, Северная Голландия; второе издание, 1999 г.