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

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

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

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

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

j(x)=x+1, j(y)=12y, y(a, b, c)=ab+c, l(b)=bⁿ и т.п.

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

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

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

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

y(n+1, a)=a ^y(n,a). (2.1)

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

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

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

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

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

y(n+1,a*)=l(y(n,a*))(2.2)

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

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

y(1, a*)= l(y(0, a*))= l(a*),

y(2, a*)= l(y(1, a*))= l(l(a*)), ...

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

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

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

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

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

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

j(0)=q, j(x¢)=l(x,j(x)). (2.3)

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

j(0, )=y( )

j(x¢₁ , )=l(x₁, j(x₁, ), ) . (2.4)

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

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

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

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

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

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

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

IV. j( )=y(l₁( ), l ₂( ), ..., l _m( )).

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

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

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

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

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

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

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

и .

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

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

j(0, x)=x, (A) j(y¢, x)=(j(y, x))¢ (B)

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

j(1, x) = (j(0, x))¢ = x¢ = x+1,

j(2, x) = (j(1, x))¢ = (x+1)¢ = x+1+1 = x+2,

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

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

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

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

2.2.2. Построение класса общерекурсивных функций

Математиками были предприняты попытки построения вычислимых функций, не являющихся примитивно-рекурсивными, и такие функции бы-ли получены. Это позволило сделать вывод, что класс примитивно-рекур-сивных функций не охватывает всех вычислимых функций и нуждается в расширении. Однако нас ограничивает, прежде всего, принятая форма индукции (схема V), которая определяет функцию j через уже известные функции l и y.

Пример 2.3. Вычислим для примера 2.2 значение j(3, 5). Формально проанализируем, какие операции нужно совершить, чтобы, пользуясь схемой (A) и (B), вычислить j(3, 5).

1. Подставим в (B) вместо переменных числа n=2, x=5. Получим

j(3, 5)=j(2, 5)+1.

2. Подставим в (B) n=1, x=5 и определим j(2, 5): j(2, 5)=j(1, 5)+1.

3. Аналогично получим j(1, 5)=j(0, 5)+1.

4. Подставим в (A) x=5. Получим j(0, 5)=5.

5. Заменим в выражении п. 3 j(0, 5) на 5, согласно п. 4:

j(1, 5)=5+1=6.

6. Заменив j(1, 5) в выражении п. 2 её значением из п. 5, получим

j(2, 5)=6+1=7.

7. Наконец, заменив j(2, 5) в выражении п. 1 её значением из п. 6, получим j(3, 5)=7+1=8.

В этом примере для организации вычислений понадобились лишь две операции:

1) подстановка чисел на место переменных;

2) замена вхождений, т. е. замена правой части в одном из равенств левой частью другого равенства (или наоборот).

Если некоторое равенство может быть выведено с помощью этих двух операций из заданной системы равенств Е, то говорят, что это равенство выводимо в системе Е. В примере 2.2 системой Е является само описание функции j(n, x).

Определение. Функция j( ) называется общерекурсивной, если существует такая конечная система равенств Е, что для любого набора чисел найдётся такое одно и только одно число y*, что равенство j( )=y* может быть выведено из Е с помощью конечного числа применений операций подстановок чисел на место переменных и замены вхождений.

Говорят, что Е рекурсивно определяет функцию j. Здесь не требует-ся, чтобы значения функции вычислялись с помощью её значений в пре-дыдущих точках; не требуется, чтобы входящие в систему Е вспомо-гательные функции были всюду вычислимы; не фиксируется никакая схема индукции. Требуется только, чтобы система равенств Е так определяла данное значение j с помощью других значений j и некоторых значений вспомогательных функций, чтобы j во всех точках можно было однозначно вычислять на основании системы Е.

Приведенное определение общерекурсивной функции не конструк-тивно, так как не раскрывает механизма вычислительной процедуры на-хождения числа y*. Можно, конечно, попробовать выводить из Евсе воз-можные равенства до тех пор, пока не встретится нужное равенство. Однако при таком подходе нет никакой гарантии, что этот процесс перебора не продлится неопределённо долго (ср. с лабиринтом).

Процессу перебора можно придать определённую регулярность, так чтобы этот процесс годился для вывода равенства j( )=y* за конеч-ное, но не ограниченное заранее число шагов.

Предварительно отметим, что равенство j( )=y* может быть представлено в эквивалентной форме y( , y)=0. Последнее равенство в общем случае имеет вид y( , y)=0; этому выражению может быть поставлен в соответствие предикат P( , y), истинный в случае y=0.

Гёдель предложил метод сведения любого алгоритма к численному алгоритму путём специальным образом организованной нумерации любых выражений (своеобразной их кодировки). Этот метод носит название гёделизации. Рассмотрим этот метод.

Включим все условия задачи, доступные для переработки данным алгоритмом A, в занумерованную неотрицательными целыми числами последовательность A₀, A₁, …, A_n. Аналогично записи возможных решений также включим в занумерованную последовательность B₀, B₁,..., B_m.

Теперь можно любой алгоритм, перерабатывающий запись условий A_n в запись решения B_m, свести к вычислению значений некоторой число-вой функции m = j(n), т.е. можно говорить об алгоритме, который перера-батывает номер записи условия в номер записи решения. Этот алгоритм будет численным алгоритмом. Очевидно, что если есть алгоритм, реша-ющий исходную задачу, то имеется и алгоритм вычисления соответ-ствующей функции. Справедливо и обратное утверждение.

Гёдель предложил рассматривать запись некоторого числа n в фор-ме n = , где p₀=2, p₁=3, p₂=5 и вообще p_m - m-е простое число.

Из этой записи видно (в силу теоремы о единственности разложения любого числа на простые множители), что каждому числу n однозначно соот-ветствует набор a₁, a₂, .., a_m и, наоборот, каждому набору a₁, a₂, ..., a_m однозначно соответствует число n. Например, при n=60 имеем: 60 = 2² 3¹ 5¹, т.е. a₁ = 2, a₂ = 1, a₃ = 1.

C помощью этого метода можно нумеровать теперь любые упоря-доченные последовательности, состоящие из m чисел. Рассмотрим следующие примеры.

1. Каждой паре чисел a₁ и a₂, для которой нужно найти её наибольший общий делитель q, может быть поставлен в соответствие гёделевский номер этой пары n = .

Алгоритм Евклида сведётся тогда к вычислению функции q =j(n).

2. Пусть требуется занумеровать все слова в некотором алфавите A. Это легко сделать, поставив в соответствие каждой букве алфавита какое-либо число. Тогда каждому слову в алфавите A будет соответствовать последовательность чисел. Проводя затем обычным способом гёделизацию, получим гёделевский номер этой последовательности. Ясно, что номер слова определяется выбранной системой соответствий между буквами и числами. Теперь легко пронумеровать все последовательности слов (например, все дедуктивные цепочки). Здесь также имеется однозначное соответствие последовательности слов и последовательности гёделевских номеров этих слов. Проведя гёделизацию вторично, можно определить гёделевский номер самой последовательности гёделевских номеров отдельных слов.

Итак, с помощью гёделизации арифметические алгоритмы сводятся к вычислению значений целочисленных функций. Аналогично любой нормаль-ный алгоритм Маркова может быть также сведен к вычислению значений целочисленных функций. Поэтому алгоритм вычисления значений целочис-ленных функций можно считать универсальной формой алгоритма.

Оказывается, что путём гёделизации процесс перебора всех выводов из Е (см. с. 68) сводится к применению оператора наименьшего числа m. Введение в рассмотрение этого оператора приводит к иному способу определения рекурсивных функций.

Оператор наименьшего числа m ставит в соответствие примитивно-рекурсивному предикату P( , y)(или примитивно-рекурсивной функ-ции y( , y), представляющей предикатP) примитивно-рекурсивную функцию j( ) следующим образом:

j( )=my| P( , y)= m y| y( , y)=0 (2.5)

при условии

( x₁)( x₂)...( x_n)( y)| P( , y),(2.6)

или

( x₁)( x₂)...( x_n)( y)|y( ,y)=0. (2.7)

Утверждение.Любая общерекурсивная функция j( ) может быть представлена в виде

j( )=t(my|y( ,y)=0), (2.8)

где y и t - примитивно-рекурсивные функции, причём для функции y справедливо выражение

( x₁)( x₂)...( x_n)( y)|y( ,y)=0. (2.9)

Типичной ситуацией применения m-оператора является построение обратных функций. Допустим, что для некоторой функции y=f(x) существу-ет обратная функция, т. е. для каждого натурального y существует един-ственное значение x, для которого f(x)=y; в таком случае обратная функция x=j(y) может быть определена посредством m-оператора:

j(y)= m x |f(x)=y. (2.10)

Многие функции анализа, такие как показательная c^x и степенная x^c , определены на всём натуральном ряде, если параметр c выбран подхо-дящим образом. Однако этого нельзя утверждать об обратных функциях; например, log_cx или , в общем случае не будет натуральным числом даже при натуральном c. В таких случаях удобно рассматривать арифме-тические варианты обратных функций, которые заключаются в следу-ющем: в качестве значений функции объявляется целая часть истинных значений функции, т. е.]j(y)[, где ]x[ - целая часть числа x. Теперь ясно, что, исходя из функции у=c^x или y=x^c, можно определить арифметические обратные функции посредством m-оператора:

]log_r(y)[ =mx | r^x+1>y;

] [ =mx |(x+1)^r >y.

Рекурсивное описание называется примитивно-рекурсивным, если в нём не участвует m-оператор, т. е. допускаются только операторы супер-позиции, введения фиктивных переменных и примитивной рекурсии.

Если к уже известным схемам определения примитивно-рекурсивных функций добавить схему VI, составленную из (2.8) и (2.9), то в результате конечного числа применений схем I-VI получим общерекурсивную функцию j( ).

Таким образом, примитивно-рекурсивные функции являются частным случаем общерекурсивных функций; всякая примитивно-рекурсивная фун-кция есть общерекурсивная функция, но не наоборот.