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

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

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

Определение и примеры

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

$0!=1,$

$(n+1)!=n!(n+1).$

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

$Fib(0)=0,$

$Fib(1)=1,$

$Fib(n+2)=Fib(n+1)+Fib(n).$

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

$g(0)=0,$

$g(n+1)=\sum _{i=0}^{n}g(i)^{n-i}.$

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

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

$f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )$

где $\langle f(0),f(1),\ldots ,f(n-1)\rangle$ – число Гёделя, кодирующее указанную последовательность.В частности

$f(0)=h(0,\langle \rangle )$

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

$h(n,s)={\begin{cases}n&{\text{if }}n<2\\s[n-2]+s[n-1]&{\text{if }}n\geq 2\end{cases}}$

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

Эквивалентность примитивной рекурсии

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

$f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )$.

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

${\bar {f}}(n)=\langle f(0),f(1),\ldots ,f(n-1)\rangle$

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

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

${\bar {f}}(0)=\langle \rangle$,

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

где add ( n , s , x ) вычисляет, всякий раз, когда s кодирует последовательность длины n , новую последовательность t длины n + 1 такую, что t [ n ] = x и t [ i ] = s [ i ] для всех i < н . Это примитивно-рекурсивная функция в предположении соответствующей нумерации Гёделя; h изначально предполагается примитивно-рекурсивным. Таким образом, отношение рекурсии можно записать как примитивную рекурсию:

${\bar {f}}(n+1)=g(n,{\bar {f}}(n))$

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

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

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

Приложение к примитивно-рекурсивным функциям

В контексте примитивно-рекурсивных функций удобно иметь средство для представления конечных последовательностей натуральных чисел как отдельных натуральных чисел. Один из таких методов, кодирование Гёделя , представляет собой последовательность положительных целых чисел. $\langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle$ как

$\prod _{i=0}^{k}p_{i}^{n_{i}}$,

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

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

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

$f(n)=h(\langle f(0),f(1),f(2),\ldots ,f(n-1)\rangle )$.

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

Когда последовательность $\langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle$ разрешено включать нули, вместо этого оно представляется как

$\prod _{i=0}^{k}p_{i}^{(n_{i}+1)}$,

что позволяет различать коды последовательностей $\langle 0\rangle$ и $\langle 0,0\rangle$.

Ограничения

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

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

Ссылки

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