Определения
Этот подход к формализации понятия алгоритма принадлежит Гёделю и Клини (1936).
Основная идея Гёделя состояла в том, чтобы получить все вычислимые функции из существенно ограниченного множества базисных функций с помощью простейших алгоритмических средств.
Множество исходных функций таково:
· постоянная функция 0(x) = 0;
· одноместная функция следования s(x) = x+1;
· функция проекции pri, 1 £ i £ k, pri(x) = xi.
Нетривиальные вычислительные функции можно получать с помощью композиции (суперпозиции) уже имеющихся функций. Этот способ явно алгоритмический.
· Оператор суперпозиции. Говорят, что k-местная функция f(x1, x2, ..., xk) получена с помощью суперпозиции из m-местной функции j(y1, y2, ..., ym) и k-местных функций g1(x1, x2, ..., xk), g2(x1, x2, ..., xk), ..., gm(x1, x2, ..., xk), если
f(x1, x2, ..., xk) = j(g1(x1, x2, ..., xk), g2(x1, x2, ..., xk), ..., gm(x1, x2, ..., xk)).
Второй (несколько более сложный) способ действует так.
· Примитивная рекурсия. При n ³ 0 из n-местной функции f и (n+2)-местной функции g строится (n+1)-местная функция h по следующей схеме:
h(x1, ..., xn, 0) = f(x1, ..., xn),
h(x1, ..., xn, y+1) = g(x1, ..., xn, y, h(x1, ..., xn, y)).
При n=0 получаем (a - константа)
f(0) = a;
f(y+1) = g(y, f(y)).
Две упомянутых способа позволяют задать только всюду определенные функции. Частично-определенные функции порождаются с помощью третьего гёделева механизма.
· Оператор минимизации. Эта операция ставит в соответствие частичной функции f:Ík+1àÍ частичную функцию h:ÍkàÍ, которая определяется так:
1) область определения Dh = {<x1,..., xk> | существует xk+1³0, f(x1,..., xk, xk+1) = 0 и < x1,..., xk, y> Î Df для всех y£ xk+1};
2) h(x1,..., xk) = наименьшее значение y, при котором f(x1,...,xk, y) =0.
Оператор минимизации обозначается так h(x1,..., xk) = my[f(x1,..., xk,y) = 0]. Очевидно, что даже если f всюду определено, но нигде не обращается в 0, то my[f(x1,..., xk, y) = 0] нигде не определено. Естественный путь вычисления h(x1,..., xk) состоит в подсчете значения f(x1,..., xk, y) последовательно для y = 0,1, 2,... до тех пор, пока не найдется y, обращающее f(x1,..., xk, y) в 0. Этот алгоритм не остановится, если f(x1,..., xk, y) нигде не обращается в 0.
Все функции, которые можно получить из базисных функций за конечное число шагов только с помощью трех указанных механизмов, называются частично-рекурсивными. Если функция получается всюду определенная, то тогда она называется общерекурсивной. Если функция получена без механизма минимизации, то в этом случае она называется примитивно-рекурсивной.
Можно легко показать [23, с.136], что введение фиктивных переменных, а также перестановка и отождествление переменных не выводят за пределы класса примитивно-рекурсивных функций и класса частично-рекурсивных функций. Это проще всего объяснить на примерах.
Введение фиктивных переменных. Если g(x1, x3) - примитивно-рекурсивная функция и f(x1, x2, x3) = g(x1,x3), то f(x1, x2, x3) - примитивно-рекурсивная функция.
Перестановка переменных. Если g(x1, x2) - примитивно-рекурсивная функция и f(x2, x1) = g(x1, x2), то f есть также примитивно-рекурсивная функция.
Отождествление переменных. Если g(x1, x2, x3) - примитивно-рекурсивная функция и f(x1, x2) = g(x1, x2, x1), то f(x1, x2) есть также примитивно-рекурсивная функция.