|
С помощью операций суперпозиции и примитивной рекурсии из простейших функций получаются только полностью определенные функции. Введем еще одну операцию – операцию минимизации функции.
Пусть имеется арифметическая функция f(x1,...,xn) (возможно частично определенная). Пусть существует какой-то механизм вычисления этой функции, причем значение функции не определено тогда и только тогда, когда этот механизм работает бесконечно, не выдавая никакого определенного результата.
Фиксируем произвольный набор значений x1,...,xn-1 для первых n-1 аргументов функции f и рассмотрим уравнение относительно y : f(x1,...,xn-1,y)=xn.
Чтобы найти натуральное решение y этого уравнения, будем вычислять при помощи указанного выше "механизма" последовательно значения f(x1,...,xn-1,a) для a=0,1,2,... и сравнивать с xn. Наименьшее значение a, для которого получится f(x1,...,xn-1,a)=xn, обозначим . /формула / Очевидно, / формула/ что является n-арной частичной функцией, которая получена операцией минимизации из функции f(x1,...,xn).
Описанный процесс нахождения y, будет продолжаться бесконечно в следующих случаях:
Значение f(x1,...,xn-1,y) не определено для каждого y;
Значения f(x1,...,xn-1,i) для i=0,1,...,a-1 определены, но отличны от xn, а значение f(x1,...,xn-1,a) не определено;
Значения f(x1,...,xn-1,y) определены для всех y=0,1,2,... и отличны от xn.
Во всех этих случаях значение / формула/ считается неопределенным. В остальных случаях описанный процесс обрывается и дает наименьшее решение y = a для уравнения f(x1,...,xn-1,y) = xn.
|
