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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теперь можно любой алгоритм, перерабатывающий запись условий A_n в запись решения B_m, свести к вычислению значений некоторой число-вой функции m = (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 =(n).

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

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

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

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

()=y| P(, y)=  y| (, y)=0 (2.5)

при условии

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

или

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

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

()=(y|(,y)=0), (2.8)

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

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

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

(y)=  x |f(x)=y. (2.10)

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

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

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

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

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

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