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

Пусть задана последовательность ф-ий ).

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

1. .

2. Для любого i=1,…,n, – есть либо элементарная функция, либо Î ψ,либо получается из предшествующих ей функций в этой последовательности с помощью одной из операций примитивной рекурсии или подстановки.

Определение. Функция f называется ПРФ относительно совокупности ψ, если существует ее ПРО относительно совокупностиψ.

Осн. свойства ПРФ относительно совокупности ψ.

1⁰. Если функция f – ПРФ относительно совокупности ), и ψ c Г, то функция f, также является ПРФ относительно совокупности функций из Г. (где Г– множество, включающее произвольные арифметические функции).

Доказательство. Пусть функция f ПРФ относительно совокупности ). Тогда существует ее ПРО относительно совокупности ψ, т.е. . Если , то в силу того что ψ c Г, . Следовательно, ПРО функции f относительно совокупности ψ является и ПРО функции f относительно совокупности Г. Отсюда следует, что f есть ПРФ относительно Г. ч.т.д.

2⁰. Если f ПРФ относительно совокупности и получается из ψ при удалении какой – то функции (где - ПРФ), т.е. , то функция f будет также ПРФ относительно совокупности .

3⁰. Если f – ПРФ относительно совокупности ) и каждая функция из ψ есть ПРФ относительно Г, то f является ПРФ относительно Г.

Доказательство.Доказательство аналогично доказательству свойства 2⁰. Рассмотрим ПРО функции f относительно совокупностиψ, т.е. . Каждая функция , где i=1,…,k принадлежит совокупности ψ. Так как каждая функция совокупности ψ является ПРФ, то некоторые из них заменим на ПРО относительно Г. Таким образом, образуем ПРО функции f относительно Г. Следовательно функция f–ПРФ относительно совокупности Г.

4⁰. Если f– ПРФ относительно совокупности ), и каждая функция из совокупности ψ, есть ПРФ, то f тоже является ПРФ.