§ 12.6. Элементарные и примитивно-рекурсивные функции

Функции вида называются арифметическими функциями, если как аргументы, так и сами функции могут принимать значения лишь из множества . В дальнейшем мы будем рассматривать только арифметические функции.

Логические функции (см. гл. I) являются частным случаем арифметических функций.

Далее мы будем придерживаться следующей системы обозначений.

Переменные обозначаются малыми латинскими буквами:

Значками функций будут служить малые греческие буквы:

Предикаты будем обозначать большими латинскими буквами:

Фиксированные числа будем обозначать теми же буквами, что приняты для обозначения переменных, добавляя сверху звездочку

Дадим теперь определение вычислимой арифметической функции и разрешимого предиката.

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

Предикат , определенный на множестве целых чисел, называется алгоритмически разрешимым или просто разрешимым, если существует алгоритм для определения значения предиката при любых значениях переменных .

Данные определения являются интуитивными, неточными определениями, поскольку еще не было сформулировано точно определение вычисляющего алгоритма.

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

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

Вычислимость элементарных функций не вызывает сомнений, поскольку хорошо известны алгоритмы для выполнения всех действий, допустимых при построении элементарных функций.

В качестве исходного числа для построения элементарных функций можно было бы взять лишь число 1, ибо

Приведем примеры элементарных функций:

1) Элементарными функциями являются все простые функции вида

2) Многие из часто употребляемых функций элементарной теории чисел являются элементарными. Например:

Функция может быть выражена через функцию :

С помощью легко строится :

в) Неравенство эквивалентно равенству или .

Тогда предикат "х меньше или равен у" можно записать в виде

Действительно, если , т. е. соответствует истинному высказыванию; в противном случае .

г) Впоследствии нам пригодится функция

Это элементарная функция, ибо ее можно представить в виде

д) Остаток от деления а на

Возникает вопрос: шире ли класс всех вычислимых функций класса элементарных функций? Можно ли построить вычислимую функцию, не являющуюся элементарной?

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

Возведение в степень, в свою очередь, есть итерация умножения:

Эта функция является еще элементарной, так как она выражается через произведение. Растет эта функция с ростом а и весьма быстро.

Построим еще более быстро растущую функцию, являющуюся итерацией возведения в степень:

и вообще

Эта функция растет чрезвычайно быстро. Можно доказать (см. ), что с помощью построения элементарных функций уже невозможно «угнаться» за ростом функции точнее, что эта функция, начиная с некоторого , мажорирует все элементарные функции, т. е. для любой элементарной функции <р (а) найдется такое число , что будет выполняться неравенство

для всех . Но тогда легко показать, что функция не является элементарной.

Действительно, если бы была элементарной функцией, то нашлось бы число (можно считать в силу монотонности функции ) такое, что при . Это неравенство должно, в частности, выполняться и при , так . Получаем при этом , что невозможно.

Таким образом, итерация возведения в степень позволяет получить неэлементарную функцию. В то же время заведомо вычислима. Действительно, пусть мы хотим вычислить значение при любых . Общую формулу для определения функции мы записали так (12.3):

или:

Обозначим -элементарная, всюду однозначная вычислимая функция. Алгоритм ее вычисления сводится к повторенному раз умножению на . Запись

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

Достаточно задать теперь начальное значение , чтобы получить вычислительную процедуру, дающую последовательно значения

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

Из построенного примера мы делаем вывод, что для построения всех вычислимых функций вдасс элементарных функций нуждается в расширении. Рассмотрим с этой целью подробнее способ определения функции . Эта функция была задана по индукции: было задано начальное значение функции — базис, и был указан способ подсчета последующих ее значений по предыдущим с помощью допустимых операций.

Попробуем положить метод математической индукции в основу определения вычислимой функции. Для этого сперва несколько уточним и расширим схему определения по индукции.

Определение по индукции можно, вообще говоря, ввести на любом упорядоченном множестве, где определены понятия «предыдущий» и «следующий».

Обозначим через функцию «гследования за», которая означает переход к следующему элементу заданного множества. Если заданное множество — множество натуральных чисел

Здесь функция следования совпадает с функцией .

Если же в качестве исходного множества задано упорядоченное множество четных чисел . то и т. д. и вообще .

Мы, как правило, будем применять функцию следования для множества натуральных чисел, и поэтому всюду в дальнейшем можно операцию «штрих» понимать как прибавление единицы: .

Общую схему определения функции теперь можно уточнить следующим образом:

1) Задано .

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

В более общем случае могут присутствовать еще и неизменяемые в процессе индукции параметры . Схема тогда будет иметь вид

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

Посмотрим теперь, какие арифметические функции могут быть определены по индукции и насколько широк класс таких функций.

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

Первоначально известными или просто первоначальными будем считать следующие функции:

— описанная выше функция следования, примененная для множества натуральных чисел. Сокращенно обозначается буквой .

II. , где — функция-константа. Сокращенно обозначается — функция тождества .

Сокращенно обозначается .

Кроме схемы определения по индукции (12.5) или (12.6), в число допустимых операций включим схему подстановки IV.

IV. .

Выпишем теперь все схемы в одну колонку, друг под другом:

Здесь схемы I—III задают первоначальные функции и как бы играют роль аксиом, а IV и V — правил вывода.

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

Будем говорить, что некоторая функция непосредственно зависит от других функций, если она удовлетворяет схеме IV при каких-нибудь типе какими-нибудь (в этом случае непосредственно зависит от ), или V, а или V, б при каком-нибудь q с какими-нибудь (в этом случае непосредственно зависит от ).

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

Примитивно-рекурсивное описание — это, по сути дела, выписанный ряд функций, последовательно получаемых в результате применения схем I—V при выводе функции . Действительно, мы отправляемся от первоначальных функций, которые должны стоять в начале последовательности, и дальше, шаг за шагом, движемся к функции .

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

1) Определим функцию так:

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

и вообще

Составим теперь примитивно-рекурсивное описание этой функции. Для этого полностью выпишем схему

V, б, которой мы пользуемся при определении :

В рассматриваемом примере функция имеет вид , т. е. является первоначальной функцией тождества (я).

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

Примитивно-рекурсивным описанием функции будет последовательность Добавляя к этой последовательности функцию. , от которой непосредственно зависит функция по схеме (12.7), получим примитивно-рекурсивное описание :

2) Для определения следующей примитивно-рекурсивной функции воспользуемся тем, что сумма у определена уже как примитивно-рекурсивная функция. Зададим

Последовательно имеем

и вообще

Следовательно, произведение также является примитивно-рекурсивной функцией.

3) Используя результаты примера 2), определим

Нетрудно проверить, что определенная так функция будет представлять собой возведение в степень: .

4) . Легко видеть, что .

5) Определим функцию «предшественника

Это — примитивно-рекурсивная функция, так как она определяется по схеме V, а

6) Встречавшаяся раньше функция у определяется так:

7) Функция может быть теперь определена с помощью применения схемы IV:

12) Остаток от деления у на (эту функцию обозначают через ) определяется так:

13) определяется так:

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

Действительно,

В числе определенных нами примитивно-рекурсивных функций оказались сумма , модуль разности , произведение , частное а также конечные суммы и произведения. Следовательно, все элементарные функции, о которых говорилось в начале параграфа, примитивно-рекурсивные. Это значит, что класс элементарных функций является подклассом класса примитивно-рекурсивных функций.