2.2.1. Построение класса примитивно-рекурсивных функций

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

Определение. Функция y=(x₁, x₂, ..., x_n) называется алгоритмически вычислимой (просто вычислимой), если существует алгоритм, позво-ляющий определить значение функции y при любых значениях пере-менных х₁, х₂, ..., х_n.

Определение. Предикат Р(х₁, х₂, ..., х_n), определённый на множестве целых чисел, называется алгоритмически разрешимым (просто разреши-мым), если существует алгоритм для определения значений предиката Р при любых значениях переменных х₁, х₂, ..., х_n.

Эти определения являются неточными, поскольку ещё не сформули-ровано точно понятие алгоритма. Для их уточнения построим класс вычис-лимых функций, начав с элементарных. Элементарными являются все функции вида

(x)=x+1, (y)=12y, (a, b, c)=ab+c, (b)=bⁿ и т.п.

Рассмотрим эти функции подробнее. Если в функции (x)=x+1 поло-жить x=0 (начальное значение) и затем многократно использовать эту формулу с предыдущим значением, то таким путём можно получить все числа натурального ряда. Многократное применение одной и той же формулы (вычислительного процесса) называют итерацией. Операцию сложения двух чисел a+b можно представить как применение формулы x+1 b раз, если в качестве начального значения x положить a; таким образом, сложение двух целых чисел - это итерация добавления единицы. Нетрудно видеть, что произведение an=a+a+...+a  n раз повторенное сложение (умножение  итерация сложения).

Функция  может быть представлена в виде =d+c, где d=ab, так что  включает в себя две операции: умножение как итерацию сложения и операцию сложения как итерацию добавления единицы (в последнем случае полагаем d начальным значением для x  см. функцию f). Все эти функции растут довольно медленно, и по этому признаку их относят к элементарным.

Рассмотрим операцию возведения в степень. Для функции (b) име-ем bⁿ= bb...b - n раз повторенное умножение на число b, т. е. это итерация умножения: bⁿ =. Эта функция, хотя и растёт довольно быстро, является ещё элементарной, так как она выражается через произведение.

Построим еще более быстро растущую функцию, которая является итерацией возведения в степень: (0, a)=a, 1, a)=a^a, (2, a)=a и в общем виде

(n+1, a)=a^(n,a). (2.1)

Функция (2.1) растёт чрезвычайно быстро; эта функция, начиная с некоторого а=а*, мажорирует все элементарные функции, т. е. для любой элементарной функции (a) найдётся такое число n*, что будет выполняться неравенство (а)<(n*, a) для всех аа*.

Таким образом, итерация возведения в степень позволяет получить неэлементарную функцию. В то же время (n, a) заведомо вычислима. Действительно, пусть необходимо вычислить значение (n, a) при любых n=n*, a=a*. При a=a* формула (2.1) даёт

(n+1, a*)=(a*)^{(n, a*)} . ( 2.1’)

Обозначим (a*)^mmm) - элементарная, всюду однозначно вы-числимая функция. Алгоритм её вычисления сводится к повторенному m раз умножению на a^*.

Запись (см. (2.1’))

nn

связывает значение функции в данной точке с её значением в преды-дущей точке.

Достаточно теперь задать начальное значение (0, a*) = a*, чтобы получить вычислительную процедуру, которая последовательно даёт сле-дующие значения:





Этот процесс следует продолжать, пока не будет достигнуто зна-чение (n*, a*).

Очевидно, этим способом функция  определена всюду и однознач-но, так как вычисление её значений сводится к вычислению значений функции (m), которая является всюду определённой и однозначной.

Рассмотрим подробнее способ определения функции (n, a). Эта функция была задана по индукции: было задано начальное значение фун-кции 0, a) и был указан способ вычисления её значения по предыдущим значениям с помощью допустимых операций. Как видим, был применён метод математической индукции. Используем этот метод в качестве основы для определения вычислимой функции. Но сперва несколько уточним и расширим схему определения по индукции.

Обозначим через x функцию “следовать за”, которая означает пере-ход к следующему элементу заданного множества; для множества нату-ральных чисел функция x совпадает с x+1. Общую схему определения вычислимой функции (x) теперь можно уточнить таким образом:

1) задано (0);

2) для любого x указывается, каким образом значение (x) выражается в терминах x и (x):

(0)=q, (x)=(x,x)). (2.3)

Вболее общем случае в функции могут присутствовать ещё и неизменяемые в процессе индукции параметры x₂, x₃, ..., x_n (обозначим (). Схема (2.3) тогда будет иметь вид

(0,)=()

x_=x_x₁,) . 

Если фунции  и  известны и вычислимы, то с помощью схемы (2.4) для заданных x₂=x₂*, x₃=x₃*, ... может быть организована процедура вычисления последовательно (1, ), (2, ) и т. д. Значит, схема, заданная выражениями (2.4), действительно определяет вычислимую функцию.

Добавим к описанной выше функции x также функцию-константу и функцию-тождество. Эти три функции будем считать первоначально изве-стными, или просто первоначальными.

Итак, получены такие первоначальные функции:

I. (x)=x  описанная выше функция следования, применённая для множества натуральных чисел.

II. ()=q  функция-константа.

III. ()=x_i  функция-тождество.

Далее включим в число допустимых операций схему подстановки:

V___

И наконец, введём в систему допустимых операций схемы (2.3) и (2.4) определения вычислимой функции:

Va - соответствует схеме (2.3);

Vb - соответствует схеме (2.4).

Итак, схемы I-III задают первоначальные функции (они играют роль аксиом), а IV и V - правила вывода. Применяя многократно эти схемы, можно построить обширный класс вычислимых функций.

Определение. Функция () называется примитивно-рекурсив-ной, если она может быть построена с помощью конечного числа приме-нений схем I-V.

Это определение раскрывает механизм построения класса прими-тивно-рекурсивных функций; этот класс включает в себя подкласс всех элементарных функций.

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

и .

Рассмотрим пример построения примитивно-рекурсивной функции.

Пример 2.2. Определим функцию (y, x) так:

(0, x)=x, (A) (y, x)=((y, x)) (B)

Согласно этой схеме имеем

(1, x) = ((0, x)) = x = x+1,

(2, x) = ((1, x)) = (x+1) = x+1+1 = x+2,

(3, x) = ((2, x)) = (x+2) = x+3, и вообще (y, x)=x+y .

Назовём представляющей функцией предиката P() такую функцию (), которая обращается в нуль лишь для тех и только тех x₁, x₂, ..., x_n, для которых P() истинно. Тогда истинность P() соответствует равенству () = 0.

Определение. Предикат называется примитивно-рекурсивным, если су-ществует примитивно-рекурсивная функция, представляющая этот предикат.

Из сущности механизма построения класса примитивно-рекурсивных функций видно, что каждая примитивно-рекурсивная функция является вычислимой. Верно ли обратное утверждение: всякая вычислимая функция - примитивно-рекурсивная? Иначе: все ли вычислимые функции охватывает этот механизм? Ответ на этот вопрос даётся в подразд. 2.2.2.