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

В качестве простейших функций в теории рекурсивных функций приняты следующие:

1. – константа «ноль».

2. – «последователь».

3. – функция тождества или выбора аргумента, проекция.

Оператор суперпозиции (подстановки) – подстановка в функцию от переменных функций от переменных, что дает новую функцию от переменных.

Суперпозицией функций и называют функцию:

;

.

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

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

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

Пример 1. Константа a получается путем суперпозиции функций и :

Пример 2. Операция сложения может быть определена с помощью оператора примитивной рекурсии:

Таким образом, функция получена из простейших и путем применения оператора примитивной рекурсии, что соответствует определению примитивно-рекурсивной функции.

Пример 3. Примитивная рекурсивность операции умножения доказывается с использованием сложения:

Пример 4. Примитивная рекурсивность операции возведения в степень доказывается следующим образом:

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

Арифметическое вычитание:

Для доказательства примитивной рекурсивности вначале рассмотрим операцию : ;

т.е. операция – примитивно-рекурсивна.

Дополнительное свойство:

.

арифметическое вычитание – примитивно-рекурсивно.

Пример 6. Функция – аналог функции для натуральных чисел.

Функция примитивно-рекурсивна:

– антисигнум, функция обратная .

.

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

Отношение называется примитивно-рекурсивным, если примитивно-рекурсивна его характеристическая функция :

Пример 8. Отношение – примитивно-рекурсивно.

Действительно, .

Отношение примитивно-рекурсивно.

Действительно, .

Отношение примитивно-рекурсивно.

Действительно, .

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

Зафиксируем набор значений аргументов и рассмотрим уравнение относительно y: ; чтобы найти решение этого уравнения, натуральное , будем вычислять последовательность значений:

для ..

Наименьшее целое неотрицательное значение , удовлетворяющее этому уравнению: обозначим:

.

Говорят, что функция получена из функции операцией минимизации, если:

.

Оператор минимизации работает бесконечно в одном из следующих случаев:

1) значение не определено;

2) значение для определены, но не равны нулю, а значение – не определено;

3) значение определены для всех , но не равны нулю.

Оператор минимизации является удобным средством получения обратных функций: вычитание, деление, извлечение корня и так далее.

Пример 9. Определение операции «вычитание»:

.

Пример 10. Определение операции «деление»:

.

Пример 11. Определение операции «извлечение корня»:

.

Пример 21. Определение операции «логарифм»:

Пример 13. Процесс вычисления функции с помощью оператора минимизации приведен ниже:

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

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

Общерекурсивная функция –всюду определенная частично-рекурсивная функция.

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