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

Оператор минимизации.

В теории рекурсивных функций важную роль играет действие нахождения данной функции φ (z) значения z, которая является наименьшим корнем уравнения φ (z)=0. Выполняющий это действие оператор является оператором минимизации или µ - оператор. Существует несколько разновидностей.

Сначала рассмотрим ограниченный µ-оператор.

Ограниченный µ-оператор равен наименьшему значению y, удовлетворяющему условию

Замечание: Ограниченный µ-оператор по данной n-местной функции f строит новую функцию, значение которой равно наименьшему y, удовлетворяющему условию (1). Следствия описания оператора необходимо дополнить еще 1 условием. Пример ф-я

Неограниченный оператор минимизации

Переход f к g называется неограниченным µ-оператором минимизации и обозначается:

g( … )= [f( … , y)=b]

Частично рекурсивные функции. Определение

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

Замечание:

1) Из определений ПРФ и ЧРФ следует что множество ПРФ содержится в множестве ЧРФ.

ПРФ ЧРФ

2) Ограничения y≤ z в ограниченном µ- операторе даёт гарантию окончания вычислений, поскольку оно ограничивает сверху число вычислений корня уравнения:

f(x1, …, xn-1, y) = 0

Такое ограничения является существенной особенностью примитивно рекурсивных функций, а не ограниченный рекурсивный µ оператор такими свойствами не обладает, а потому не является примитивно – рекурсивной

Всюду определённая ЧРФ называется общерекурсивной

ОРФ ЧРФ

Из этих двух возникает гипотеза:

ПРФ ЧРФ

ОРФ ЧРФ ПРФ=ЧРФ-?

По аналогии с тем что (x) является ЧРФ, но не является ПРФ. Есть ОРФ-ии которые не являются ПРФ-ми.

Первый пример такой функции (всюду определяемая и вычислимая) придумал немецкий математик Аккерман.