15-§. Структура примитино рекурсивных функций. Реализация алгоритма на машине Тьюринга

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

(Читается: «наименьшее   такое, что  ».)
Аналогично определяется функция многих переменных:

Переход от функции к функции  принято называть применением  -оператора.
Для вычисления функции  можно предложить следующий алгоритм:

1. 
   Вычислим  . 
   

Если это значение f равно нулю, то полагаем 
=0.
Если , то переходим к следующему шагу.
2.Вычислим  .
Если  , то полагаем  =1.
Если же, не равно 1 то переходим к следующему шагу. И т.д.
Если окажется, что для всех у функция
,
то функцию  в этом случае считают неопределенной.
Но возможно, что существует такое  , что  и, значит, есть и наименьшее  , при котором C;
и в то же время может случиться, что при некотором
значение функции  не определено. Очевидно, что в этом случае процесс вычисления наименьшего  , при кото­ром  не дойдет до . 
И здесь функцию считают неопределенной.
Пример 3. Рассмотрим функцию  которая может быть получена с помощью оператора минимизации

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

4.