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

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

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

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

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

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

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

, , , +, ,

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

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

Свойство 1.
Если функция f - ПРФ относительно совокупности Ψ = {Ψ1, Ψ2, ..., Ψn}, и Ψ⊆Γ, то функция f также является ПРФ относительно совокупности функций из Γ (где Γ - множество, включающее произвольные арифметические функции).
Доказательство.
Пусть функция f ПРФ относительно совокупности Ψ = {Ψ1, Ψ2, ..., Ψn}. Тогда существует ее ПРО относительно совокупности Ψ, т.е. φ1, ..., φn. Если φi∈Ψ, то в силу того, что Ψ⊆Γ, φi∈Γ. Следовательно, ПРО функции относительно совокупности Ψ является и ПРО функции f относительно совокупности Γ. Отсюда следует, что f есть ПРФ относительно Γ. Что и требовалось доказать.

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

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

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

Свойство 4.
Если f - ПРФ относительно совокупности Ψ = {Ψ1, Ψ2, ..., Ψn}, и каждая функция из совокупности Ψ, есть ПРФ, то f тоже является ПРФ.

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




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