19) Примитивно рекурсивные функции (определение и примеры). Примитивно рекурсивные функции

Определение

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

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

 

К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов:

         Нулевая функция  — функция без аргументов, всегда возвращающая 0.

         Функция следования одного переменного, сопоставляющая любому натуральному числу  непосредственно следующее за ним натуральное число x + 1.

         Функции   ( где )  от n переменных, сопоставляющие любому упорядоченному набору    натуральных чисел число из этого набора.

 

Операторы подстановки и примитивной рекурсии определяются следующим образом:

 

         Оператор суперпозиции. Пусть f — функция от m переменных, а  — упорядоченный набор функций от n переменных каждая. Тогда результатом суперпозиции функций в функцию   называется функция   от   переменных, сопоставляющая любому упорядоченному набору    натуральных чисел число 

         Оператор примитивной рекурсии. Пусть — функция от n переменных, а   — функция от n + 2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n + 1 переменной вида

 

В данном определении переменную y можно понимать как счетчик итераций, f — как исходную функцию в начале итерационного процесса, выдающего некую последовательность функций n переменных, начинающуюся с f,    g — как оператор, принимающий на вход n переменных , номер шага итерации    ,  функцию  на данном шаге итерации, и возвращающий функцию  на следующем шаге итерации.

 

Множество примитивно рекурсивных функций — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.

 

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

 

Примеры

 

Укажем на ряд широко известных арифметических функций, являющихся примитивно рекурсивными.

 

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