Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

Например, осуществляя операцию суперпозиции функций f{x) =

При суперпозиции функции ^(л:) с самой собой получим функ­ цию h(x) = х + 2 и т. п.

Операция суперпозиции обозначается символом S n + i , где индекс сверху означает число функций.

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

Пусть заданы какие-нибудь числовые частичные функции: п- местная g я п + 2-местная h. Говорят, что п + 1-местная частичная функция f возникает из функций g и h примитивной рекурсией, ес­

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

В соответствии с этим операцию примитивной рекурсии будем применять и для п = 0, говоря, что одноместная частичная функ­ ция / возникает примитивной рекурсией из постоянной одноместной функции, равной числу а, и двуместной частичной функции h, если

/ ( 0 ) = а ; f(x+l)=h(x, /(*)).

Встает вопрос, для каждых ли g и h существует функция / и будет ли она единственной. Область определения функции — мно­ жество всех натуральных чисел, поэтому ответ на оба вопроса по­ ложительный.

Если / существует, то из (3) и (4) находим:

и поэтому / определена однозначно. Таким образом, для любых частичных n-местной функции g и п + 2-местной функции h/n = = 0, 1, 2, . . . существует только одна частичная п + 1-месГная

20

функция /, возникающая из g и h примитивной рекурсией. Симво­ лически пишут f = R{g, К).

Из (5) видно, что если мы каким-то образом умеем находить значение g и h, то значение / можно вычислить при помощи проце­

ций можно построить двуместную функцию суммирования f (х, у) = = х + у.

Эта функция определяется с помощью тождественной функции g{x) = х и функции непосредственного следования:

h[x, у, г) = z + 1.

В самом деле, используя правила (3) и (4), имеем:

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

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

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

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

Двуместная функция f{x, у) =х + у удовлетворяет соотноше­ ниям:

х + 0 = х = Ц (х) —тождественная функция;

2i

тать частичной двуместной функцией от х и у, определенной лишь для х^у, так как отрицательные числа не входят в рассматривае­ мую область. Но примитивно рекурсивные функции всюду опреде­ ленные. Поэтому в теории примитивно рекурсивных функций вместо обычной разности вводят усеченную разность, обозначаемую сим­ волом— и определяемую следующим образом:

В отличие от простой разности усеченная разность в области натуральных чисел всюду определенная, и в то же время она очень просто связана с обычной разностью. Так, например, согласно оп­ ределению (*):

Обе последние функции примитивно рекурсивны, поэтому и функция

.х—у — примитивно рекурсивная.

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

22

перпозиции, примитивной рекурсии и наименьшего корня, называ­

ция вычислима путем определенной процедуры механического ха­ рактера.

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

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

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

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

23