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

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

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

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

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

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

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

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

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

куда это Число Гёделя кодирование указанной последовательности, в частности

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

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

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

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

.

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

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

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

,

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

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

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

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

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

,

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

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

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

.

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

Когда последовательность может включать нули, вместо этого он представлен как

,

что позволяет различать коды для последовательностей и .

Ограничения

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

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

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

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