Определение операций суперпозиции, примитивной рекурсии и минимизации

На множестве определим три операции: (суперпозиция), (примитивная рекурсия) и (минимизация).

Операция суперпозиции вводится так же, как и для булевой алгебры

Операция примитивной рекурсии определяется следующим образом.

Пусть и – произвольные функции из . Построим функцию , используя «схему» примитивной рекурсии:

, .

Пусть – произвольный набор чисел из . Полагаем

.

Если на этом наборе определена, то полагаем

.

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

Операция минимизации определяется следующим образом. Пусть – произвольная функция из . Построим функцию через оператор минимизации

,

что означает, что для произвольного набора составляется уравнение

.

а) Если существует из , являющееся решением этого уравнения, то берем минимальное из решений, обозначаем его через и полагаем

.

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

Про функцию говорят, что она получена из функции при помощи операции минимизации.

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

I. Множество всех функций, которые можно получить из системы при помощи операций , и , называемое классом частично-рекурсивных функций.

II. Класс рекурсивных функций, т. е. множество всех всюду определенных функций из .

III. Класс примитивно-рекурсивных функций, т. е. множество всех функций, которые можно получить из системы при помощи операций и .

Очевидно, что

.