Рекурсия курса значений - Course-of-values recursion

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

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

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

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

${\displaystyle 0!=1,}$

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

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

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

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

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

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

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

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

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

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

${\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 )}$

предоставляет начальное значение рекурсии. Функция час может проверить свой первый аргумент, чтобы предоставить явные начальные значения, например, для 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[я] обозначает извлечение элемента я из закодированной последовательности s; легко увидеть, что это примитивная рекурсивная функция (при условии, что используется соответствующая гёделевская нумерация).

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

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

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

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

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

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

Таким образом ${\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))),}$

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

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

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

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

Данный ${\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}}}$,

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

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

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

${\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 }$.

Ограничения

Не каждое рекурсивное определение можно преобразовать в примитивное рекурсивное определение. Один известный пример: Функция Аккермана, который имеет вид А(м,п) и доказуемо не является примитивно рекурсивным.

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

Рекомендации

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