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

    На этом шаге мы рассмотрим основные свойства примитивно рекурсивные функций относительно совокупности функций.

    Пусть задана последовательность функций Ψ = {Ψ₁, Ψ₂, ..., Ψ_n}

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

1. φ_n = f;
2. Для любого i = 1, 2, ..., n φ_i - есть либо элементарная функция, либо принадлежит совокупности Ψ, либо получается из предшествующих ей функций в этой последовательности с помощью одной из операций примитивной рекурсии или подстановки.

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

    Например, функция является ПРФ относительно совокупности Ψ={x+y}. Тогда ПРО данной функции относительно Ψ={x+y} можно считать последовательность следующих функций:

, , , +, ,

    В данной последовательности функций через "+" обозначена функция f(x,y) = x + y.

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

Свойство 1.

Если функция f - ПРФ относительно совокупности Ψ = {Ψ₁, Ψ₂, ..., Ψ_n}, и Ψ⊆Γ, то функция f также является ПРФ относительно совокупности функций из Γ (где Γ - множество, включающее произвольные арифметические функции).

Доказательство.

Пусть функция f ПРФ относительно совокупности Ψ = {Ψ₁, Ψ₂, ..., Ψ_n}. Тогда существует ее ПРО относительно совокупности Ψ, т.е. φ₁, ..., φ_n. Если φ_i∈Ψ, то в силу того, что Ψ⊆Γ, φ_i∈Γ. Следовательно, ПРО функции относительно совокупности Ψ является и ПРО функции f относительно совокупности Γ. Отсюда следует, что f есть ПРФ относительно Γ. Что и требовалось доказать.

Свойство 2.

Если f - ПРФ относительно совокупности Ψ = {Ψ₁, Ψ₂, ..., Ψ_n} и Ψ' получается из Ψ при удалении какой-то функции Ψ_j (где Ψ_j - ПРФ), т.е. Ψ' = Ψ \ {Ψ_j}, то функция f будет также ПРФ относительно совокупности Ψ'.

Доказательство.

Пусть имеется ПРО функции а относительно совокупности Ψ = {Ψ₁, Ψ₂, ..., Ψ_n}. А также известно, что Ψ_j∈Ψ, (где j = 1, 2, ..., n) является ПРФ. Пусть Ψ' = Ψ \ {Ψ_j}. Далее поступаем следующим образом. Рассмотрим ПРО функции f относительно совокупности Ψ = {Ψ₁, Ψ₂, ..., Ψ_n}. Относительно принадлежности функции Ψ_j к данной последовательности функций, возможно два случая. Либо она принадлежит данной последовательности функций, либо не принадлежит. В рассматриваемом ПРО, если функция не встречается, то это ПРО оставляем без изменения

    Очевидно, его можно считать ПРО функции f относительно совокупности Ψ' = Ψ \ {Ψ_j}. В случае, когда в рассматриваемом ПРО функции f относительно совокупности Ψ, встречается функция Ψ_j, то перед первым ее появлением в ПРО вместо Ψ_j записываем ее ПРО. Тогда полученная последовательность функций является ПРО функции f относительно совокупности Ψ' = Ψ \ {Ψ_j}. Что и требовалось доказать.

Свойство 3.

Если f - ПРФ относительно совокупности Ψ = {Ψ₁, Ψ₂, ..., Ψ_n} и каждая функция из Ψ есть ПРФ относительно Γ, то f является ПРФ относительно Γ.

Доказательство.

Доказательство аналогично доказательству свойства 2. Рассмотрим ПРО функции f относительно совокупности Ψ, т.е. φ₁, ..., φ_k. Каждая функция φ_i, где i = 1, 2, ..., k принадлежит совокупности Ψ. Так как каждая функция совокупности Ψ является ПРФ, то некоторые из них заменим на ПРО относительно Γ. Таким образом, образуем ПРО функции f относительно Γ. Следовательно функция f - ПРФ относительно совокупности Γ.

Свойство 4.

Если f - ПРФ относительно совокупности Ψ = {Ψ₁, Ψ₂, ..., Ψ_n}, и каждая функция из совокупности Ψ, есть ПРФ, то f тоже является ПРФ.

    На следующем шаге мы рассмотрим производные операции над функциями.

Предыдущий шаг Содержание Следующий шаг