и, значит, из примитивной рекурсивности функции [ж/г/]; будет вытекать и примитивная рекурсивность функции rest {х, у).

Согласно определению при г/ > О число [х/у] = п удовлетворяет соотношениям

nyxin 1)у.

Отсюда видно, что л равно числу нулей в последовательности

iy X, 2у -- X, . ., пу X, . . ., ху X. Поэтому для г/ > о имеем формулу

{xjyl % щ{1ух).

Непосредственная проверка показывает, что формула (1) верна и при г/ = 0. Так как функция sg [iy - х), стоя-П1;ая под знаком суммы, примитивно рекурсивна, то на основании теоремы 1 заключаем, что функция [xfy], а вместе с ней функция rest {х, у) примитивно рекурсивны.

Говорят, что число X делится (без остатка) на число у, или что у делит х, если rest (х, у) = 0. Введем двуместную функцию div {х, у) полагая по определению

1, если rest (а;, г/) = О,

.0, если rest {х, у) Ф 0.

Очевидное соотношение

div (ж, у) = sg rest {х, у)

показывает, что функция div примитивно рекурсивна. Полагаем также по определению

div [х, у)

nda;= 2 div {x,t).

Если хфО, то делители числа х не превосходят х и потому для полояштельных значений х число nd х совпадает с числом различных делителей х (включая число 1). Из формулы (2) видно, что фзгнкция nd примитивно рекурсивна.

В арифметике натуральное число х называется простым, еслп оно имеет точно 2 различных делителя. Число О имеет бесконечно много, а число 1 лишь один делитель. Поэтому О и 1 - не простые числа. Для простых чисел 2, 3,

5 7, . . . введем стандартные обозначения р = 2, pi = \L 3, . . Таким образом, р„ есть {п -\- 1)-е простое число в натуральном ряде чисел.

Обозначим через %р {ii) характеристическую функцию свойства быть простым числом. Иначе говоря, положим

(„) = о для п простого и Xv (") = 1 для п непростого. Так как простые числа и только они имеют ровно 2 делителя, то

%p{x)=sg\ndx~ 2\

п, следовательно, функция Хр {х) примитивно рекурсивна.

Одной из наиболее известных арифметических функций является функция п {х), равная количеству простых чисел, не превосходящих х. Очевидная формула

n{x)=Z sgXpW

показывает, что функция я {х) примитивно рекурсивна.

Из определения функции п {х) непосредственно следует, что

(Рп) = п + 1, п {х) <С п + i, если X < рп-

Отсюда видно, что х = р„ есть минимальное решение уравнения п (х) = п 1. Поэтому

Рп = Р{п) = \1х{\ {X) - (га ч- 1) I = 0).

Стоящая под знаком [.1-операцш1 функция \ п {х) - ~ (п -{- 1)1 примитивно рекурсивна. В силу теоремы о мажорируемых неявных функциях (п. 3.1) для доказательства примитивной рекурсивности функции р (п) остается лишь найти примитивно рекурсивную функцию а (п) такую, чтобы для всех п было р„ < ос (я). Из теории чисел хорошо известно, что в качестве функции а {п) можно взять 2 .

В самом деле, требующееся нам неравенство

Рп < 2" (3)

заведомо истинно при п = 0. По индукции далее предполагаем, что неравенство (3) истинно для всех значений п, меньших некоторого числа s -f- 1. Докажелг, что (3) истинно и для п = S -f- 1. По предположению имеем

р,р, . . . -f К 2°+2.+...W» + 1 < 2-".

Число а = рарх . . . р + i больше единицы и потому ДОЛЖНО иметь какой-то простой делитель р,.. Этот делитель ; не может совпадать ни с одним из простых чисел р, pi, . . . . . ., Ps, так как при делении числа а на любое из чисел Ра, Pi, • , Ps получается остаток 1. Но все простые числа, не превосходящие Ps, содержатся в последовательности Ро, Ръ ., Ps- Число рг в нее не входит и потому Ps+i < Рг- Так как р < а, то

Ps.-i < а < 22",

что и требовалось.

Итак, неравенство (3) доказано, а вместе с ним доказана и примитивная рекурсивность функции р (ж) = р.

Введем еще одну важную для дальнейшего функцию. Эту функцию будем обозначать через ех {х, у) или, сокращенно, ехху и называть экспонентой числа рх в числе у. По определению при у полагаем ex у равным показателю наивысшей степени простого числа рх, на которую делится у. Для г/ = О полагаем по определению ехО = О для всех значений х. Например,

ехо 8 = 3, exi 8 = О, ехо 0 = 0.

Каждое натуральное число л > 1 можно однозначно представить в виде произведения

п = рЫг -Pil {aj > О, io<h<. . .<is)

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

exj„ п = Uq, . . exjj п = Us

и exj я = О для всех значений i, отличных от io, • • •, is-Чтобы доказать примитивную рекурсивность функции ех {х, у), снова воспользуемся теоремой о мажорируемой неявной функции. По определению ех {х, у + i) есть наибольшее значение и, для которого pi есть делитель у + I. Поэтому можно утверждать также, что ех {х, у -Ь 1) есть

наименьшее значение и, для которого рТ не делит у + i, то есть

ех {х, у + i) = }х„ (ii rest {у + i, р) = 0). (4)

Функция рх примитивно рекурсивна и, кроме того, ех (ж, г/ -Ы) < г/ + 1. (5)

В силу упомянутой теоремы о мажорируемых неявных функциях из (4) и (5) следует, что функция ех (ж, у + 1), а с нею и ех {х, у) = ех (х, {у i) + 1) примитивно рекурсивны.

Наконец, рассмотрим еще функцию

q{x) = x [Yxl\

где символом [z] обозначается целая часть вещественного числа Z, равная наибольшему целому числу, не превосходящему Z. Число q {х) называется квадратичным остатком числа X. Оно равно расстоянию от х до ближайшего слева точного квадрата.

Равенство п = Yx] равносильно соотношению

п<х<{п + i)\

где п - натуральное число. Таким образом,

lYx] = fit (sg {{t + 1)2 - ж) = 1)

и вместе с тед1 lYx] < х. По теореме о мажорируемой неявной функции отсюда следует, что функция lYx] примитивно рекурсивна. Вместе с нею примитивно рекурсивной является и функция q {х) - х - [Yх]- Аналогичным образом доказывается примитивная рекурсивность функции

[ Yx] и многих других арифметических функций.

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

Определение. Пусть а-у {х), . . ., aj (ж) - всюду определенные функции, удовлетворяющие для всех значений X условиям

аг (ж Ч-1)< ж (i = 1, . . ., S). (6)

Говорят, что функция f {х, . . ., Жп+х), получается возвратной рекурсией из функций g {х, . . Хп), h {х, . . ., Хщ

у, z-i, . . Zs) и вспомогательных функций а, . . ., aj если для всех значений переменных Xi, . . ., Хп, у

f {хх, . . ., Хп, 0) = g {хх, . . ., Хп), f {хх, . . ., Хп, у + i) = h {хх, . . ., Хп, у, (7)

/ {xi, . . ., Хп, «1 {у + 1)), . . ., / {хх, . . ., Хп, «3 {у + 1))).

Как и в случае примитивной рекурсии, легко доказывается, что для любых функций g, h, at, удовлетворяющих высказанным в определении условиям, функция /, удовлетворяющая требованиям (7), существует и единственна. Более того, верна следующая

Теорема! (о возвратной рекурсии). Функция / возникающая из всюду определенных функций g {х, . .. . . ., Хп), h {хх, . . ., Хп, у, Zi, . . ., Zs) и вспомогательных функций «1 (ж), . . ., «3 (х), удовлетворяющих условиям (6), с помощью возвратной рекурсии, может быть получена из тех же функций g, h, at и простейших функций о, s, Im операциями подстановки и примитивной рекурсии.

Иными словами, функция / является примитивно рекурсивной относительно функций g, h, а-, . . ., as.

Для доказательства введем новую функцию F, полагая

F{x„...,Xn,y)=f[pT--. (8)

Вспоминая определение функции ех {и, v), непосредственно заключаем, что для и у

f {хх, . . ., Хп, и) = ех {и, F {хи . . -у Хп, у)). (9)

По условию «г (г/ -Ь 1) г/. Поэтому соотношение

/ {xi, . . ., Хп, осг {у + 1)) =

ех (ai (г/ + 1), F (х, . . ., Хп, у)) (10)

верно при любых значениях х, . . ., Хп, у.

Найдем теперь пртштивно рекурсивную схему для F. Прежде всего, из (7) и (8)

F (жх, . . ., Хп, 0) = ро

В силу (8) имеем также

F {xi, . . .,Хп,у +i) = F {хх, . . ., Хп, у) Руп "" 1

Заменяя здесь терм / (хц . . ., Хп, у -\- i) его значением из (7), получим

F (хъ ...,Xn,y + i) = F (жь ...,Хп,у)х

ph{x,......т, у, .({.т,.....х, аДу+1))........ , х, aOj+m

Соотношения (И), (12) можно при помощи формул (10) представить в виде

F {xi, . . ., Хп, 0) = G (жх, . . ., Хп),

F {хх, . . ., г/ + 1) =

= Н (жх, . . ., Хп, у, F (жх, . . ., Хп, у)).

G (Жх, . . ., Хп) = Ро

, , h(x„ X , у, ех(а,(у+1), г), ех(а (y+i), z))

Н (xi, . . ., Хп, y,z) = zpui

Таким образом, функция F получается примитивной рекурсией из функций Gm Н, а функция / выражается через F согласно (9) формулой

/ (жх, . . ., Хп, у) = ех {у, F (жх, . ., Хп, у)).

Тем самым теорема 1 доказана. В качестве примера обычно приводят последовательность

0,1,1,2,3,5,8,13,21,...,

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

Ф (0) = 0, Ф (1) = 1, Ф (тг -Ь 2) = Ф (тг) + Ф (тг -Ы) или

Ф (0) = о, Ф (тг 4-1) = Ф (тг) -Ь Ф (тг 1) -Ь s"i тг.

Отсюда видно, что функция Ф (тг) возникает возвратной рекурсией из функций

g (х) = О, h {х, у, Zi, Za) = sg г/ -Ь Zi -f Z2

и вспо.могательных функций

«1 {у) = у- 1. «2 {у) = У 2.