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

1. Всякая примитивно рекурсивная функция всюду определена.

2. Если функция f получена из примитивно рекурсивных функций с применением операций суперпозиции или примитивной рекурсии, то функция f является примитивно рекурсивной функцией.

3. Все примитивно рекурсивные функции интуитивно вычислимы.

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

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

Таким образом, функция является примитивно рекурсивной.

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

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

Пример 3. Покажем, что примитивно рекурсивна. Действительно, функция получена при помощи операции примитивной рекурсии

,

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

Пример 4. Покажем, что функция является примитивно рекурсивной. Представим функцию в виде примитивной рекурсии.

,

где .

Пример 5. Покажем, что функция является примитивно рекурсивной. Представим функцию в виде примитивной рекурсии.

,

Пример 6. Покажем, что функция является примитивно рекурсивной. Представим функцию в виде примитивной рекурсии.

Пример 7. Покажем, что r(x)=|x-5| примитивно рекурсивна. Действительно, функция получена суперпозицией функций

Пример 8. Покажем, что функция является примитивно рекурсивной. Представим функцию f(x) в виде суммы (сумма является примитивно рекурсивной функцией) функций f₁(x), f₂(x) f₃(x), где , ,

Теперь покажем, что каждая из функций f₁(x), f₂(x) f₃(x) является примитивно рекурсивной, поскольку представляет собой суперпозицию примитивно рекурсивных функций.

,

,

Теорема. Пусть n- арная функция g примитивно рекурсивна. Тогда функции , , определенные следующим образом,

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

Доказательство. Из условия теоремы следует, что

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

Для функции доказательство аналогичное.

Теорема доказана.

Пример. Положим . Тогда . Поскольку функция примитивно рекурсивная, то по предыдущей теореме функция также является примитивно рекурсивной.

Теорема.

· Если п.р.ф., то также п.р.ф. (Операция введения фиктивных переменных).

· Если п.р.ф., то также п.р.ф. (Операция перестановки переменных).

· Если п.р.ф., то также п.р.ф. (Операция отождествления переменных).

Доказательство. Докажем первое утверждение. Новая функция представима в виде суперпозиции п.р.ф.

Остальные утверждения доказываются аналогично.

2.6 Частично рекурсивные функции

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

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

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

.

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

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

· Значение не определено для каждого

· Значения для определены, но отличны от , а значение не определено.

· Значения определены для всех и отличны от .

Во всех этих случаях значение считается неопределенным. В остальных случаях описанный процесс обрывается и дает наименьшее решение для уравнения .