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

Метод определения теоретико-числовых функций с помощью рекурсии

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

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

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

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

${\displaystyle 0!=1,}$

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

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

${\displaystyle Fib(0)=0,}$

${\displaystyle Fib(1)=1,}$

${\displaystyle Fib(n+2)=Fib(n+1)+Fib(n).}$

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

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

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

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

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

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

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

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

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

${\displaystyle 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 ; легко увидеть, что это примитивная рекурсивная функция (при условии использования соответствующей нумерации Гёделя).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

Ссылки

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