Т. А. Сливина математическая логика и теория алгоритмов

3. Операция минимизации ( -оператор).
Пусть задана некоторая функция f(x,y). Зафиксируем значение х и выясним, при каком у f(x, у) = 0.
Более сложной задачей является отыскание для данной функции f(x, у) и фиксированного х наименьшего из тех значений у, при которых функция f(x,y) = 0. Так как результат решения задачи зависит от х, то наименьшее значение у, при котором функция f(x, y) = 0 есть функция х. Принято обозначение

(Читается: «наименьшее у такое, что f(x,y) = 0 ».)
Аналогично определяется функция многих переменных:
.
Переход от функции к функции принято называть применением -оператора.
Для вычисления функции можно предложить следующий алгоритм:
1. Вычислим . Если это значение f равно нулю, то полагаем =0. Если , то переходим к следующему шагу.
2. Вычислим . Если , то полагаем = 1. Если же, то переходим к следующему шагу. И т.д.
Если окажется, что для всех у функция , то функцию в этом случае считают неопределенной. Но возможно, что существует такое у₀, что f(x₁,x₂,...,x_n,y₀) = 0 и, значит, есть и наименьшее у, при котором ; и в то же время может случиться, что при некотором z(0 < z < y₀) значение функции не определено. Очевидно, что в этом случае процесс вычисления наименьшего у, при кото­ром f(x_ltx₂,...,x_n,y) = 0 не дойдет до у₀. И здесь функцию считают неопределенной.
Пример. Рассмотрим функцию f(x,y) = х-у, которая может быть получена с помощью оператора минимизации

Вычислим, например, f(7,2), то есть значение функции при у = 2, х = 7. Для этого положим у = 2 и будем придавать x последовательно значения:
z = 0, 2 + 0 = 27,
z = 1, 2 + 1 = 37,
z = 2, 2 + 2 = 47,
z = 3, 2 + 3 = 57,
z = 4, 2 + 4 = 67,
z = 5, 2 + 5 = 7 = 7.
Таким образом, f(7,2) = 5.
Определение 2. Функция называется частично рекурсивной, если она может быть получена в конечное число шагов из простейших функций при помощи операций суперпозиции, схем примитивной рекурсии и -оператора.
Определение 3. Функция f(x_ltx₂,…,x_n) называется общерекурсивной, если она частично рекурсивна и всюду определена.
Примерами общерекурсивных функций являются функции:
1) ,
2) О(х),
3) ,
4) f(y, x) = у+x,
5) f(y, x) = ху,
6) f(y, x) = х+n.