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

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

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

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

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

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

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

Для построения примитивно-рекурсивных функций используются операторы суперпозиции и примитивной рекурсии.

Оператором суперпозиции называется подстановка в функцию от m переменных m функций от n переменных, что дает новую функцию от n переменных. Суперпозицией функций g и называют функцию

Пример 1. Пусть

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

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

Рис. 2.1. Алгоритм вычисления по схеме примитивной рекурсии.

Пример 2. Вычисление функции с помощью оператора примитивной рекурсии.

Пусть требуется вычислить 4!. По схеме примитивной рекурсии имеем:

Видно, что всякий раз при вычислении через значение уже определено.

Определение примитивно-рекурсивной функции

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

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

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

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

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

и :

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

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

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

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

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

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

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

Тогда:

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

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

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

При доказательстве примитивной рекурсивности не обязательно явным образом использовать оператор примитивной рекурсии.

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

Справедливость этого равенства проверьте самостоятельно.

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

1. Во-первых, следует пытаться выразить данную функцию через известные примитивно-рекурсивные функции с помощью суперпозиции.

2. Если все же необходимо явно использовать оператор примитивной рекурсии, следует поступать следующим образом:

- определить, по какой переменной проводится примитивная рекурсия;

- определить значение (формулу) исследуемой функции при нулевом значении переменной (тем самым получив первую формулу схемы примитивной рекурсии);

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

3. Следует иметь в виду, что если функция не всюду определена (т.е. частичная), то она не примитивно–рекурсивна.

Примитивно-рекурсивными могут быть не только арифметические функции, но и «арифметизованные» логические функции, отношения, предикаты, различные операторы.

«арифметизованная» логическая функция – это такая арифметическая функция, которая на множестве { 0,1 } ведет себя как логическая.

Пример 9. Операции на множестве { 0,1 } примитивно–рекурсивны

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

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

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

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

Пример 11. Доказать примитивную рекурсивность предиката «простое число».

При доказательстве воспользуемся примитивно–рекурсивными функциями (антисигнум - функция обратная ), S.

Утверждение «n - простое число» разобьем на две части:

1.

2. Из равенства следует: либо a=1, либо b=1.

Примитивная рекурсивность отношения :

Вторую часть утверждения запишем в виде:

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

Примитивная рекурсивность операции «®» (импликация) следует из примитивной рекурсивности базисных логических операторов . Следовательно вторая часть утверждения «n - простое число» тоже примитивно–рекурсивна.

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

Пример 12. Примитивная рекурсивность оператора условного перехода

где и - примитивно–рекурсивные функции; P - примитивно–рекурсивный предикат.

Примитивная рекурсивность функции (и оператора B) следует из равенства:

Дата добавления: 2014-01-07