Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

менению Щ и к счету этих повторений до тех

пор, пока их число не

достигнет

х.

Рассмотрим

алгоритмы:

х \\ т II г в

1)

Э,

перерабатывающий

тройку

чисел

тройку

1||/(г);

х в

2)

2,

перерабатывающий

число

тройку л - ||0||с ;

т мень­

ше

3) Ф, распознающий свойство: в

тройке чисел

х | | / п | | г

х.

Тогда формула «2° пока Ф,

повторяй Э» задает

алгоритм, кото­

рый,

исходя

из значения х,

вырабатывает

л-1| 0 || с, потом х || 1 || ft (с),

потом

* | J 2 | | / j (JS (с))

и т. д. до

тех пор, пока будет

получена

тройка

x-||.v|| ip (х).

Поэтому формула

2

° (пока

ф, повторяй Э)° Выд, где

Выд — стандартная

программа,

выделяющая

крайне правую ком­

поненту

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

ср. Для

получения

программы

5(ф

остается

только заготовить

про­

граммы

для алгоритмов 2, Ф,

©,

что не представляет труда.

На­

пример,

алгоритм

© описывается

формулой

£ || G || 51/,

где

6 —

программа, вычисляющая функцию s (х) =

х +

1. Итак,

класс

вы­

суперпозиции. Например, из функции f, (х) =

2х

посредством супер­

позиций

можно

получить

каждую

из

функций

I {Jt (.v)) •= 2 2 ' 1 ,

I (h U W)) =

22

и

т. д. В то же

время разовое

применение

итера­

ции

Ф

(0)

= 1,

ф

(х +

1)

=

Ь (ф

(х)),

т.

е.

ср (х

+

1) = 2'(*»

. • ^ | v этажеП

дает

функцию

Ф ( А')

=

2'-2

,

ошеломляюще

быстро

Ч>

(0)

=

с,

Ф

(Л' +

1)

=

I

(х,

Ф (Л-)).

П р и м е р . Пусть

с =

I ,

/j (х,

у) =

(х

+

1) X у . Тогда полу­

чаем примитивную

рекурсию

Ф (0)

•= 1,

ф (х

+

1) =

(х

+

1)

X ф (х).

Отсюда видно,

что

ср (1) =

1 X 1 =

1,

<р (2) =• 2 x 1 = 2 п т. д.

Вообще ф (х) =

* X

(х

— 1) X

(х — 2) ... 2-1 = х\

функции ft

В частности,

могло оказаться,

что один

из аргументов

фиктивен.

Пусть, например,

Ц (х,

у) =

q (у);

тогда

примитивно ре­

курсивная

схема

принимает

вид

Ф (0) =

с; ф (х

+

1) => q (ф (х))

и она определяет

ф как итерацию функции q. Если же I (х, у) =

г (*-),

то схема

принимает

вид

ф"(0) =

с,

Ф (Л- +

1) = г (х).

•

(ф)

В данном частном случае примитивной

рекурсии по

существу

отсутствует процесс

возвращения

от ф (

А -

+

1) и

ф (х).

В случае двуместной функции

ф исходными считаются

трехмест­

ная функция I и одноместная

g; соотношения

таковы;

Ф (0,

п)

= g (л),

Ф (х +

1. п) •= j

(дг, ф (х,

л), л).

Ф(0.

пу,

п«,

nk_])

= g(n1

п2,

пк_:),

Ф(*чМ,

«1

"г,

пк_

\) = 1(х

<р{х, пъ

n k _ 1 y \

П1.

nk-

{)•

где I, g — заданные функции

от k +

1 и к — 1 переменных,

соот­

ветственно. В схеме (*) по первому аргументу

функции ф ведется

индукция; остальные же аргументы играют роль

параметров.

П р и м е р .

Пусть

g (л) — я, [ (х, у , п) =

х

X у

X п. Тогда

в соответствии

со

схемой

Ф (0,

п)

=

я, Ф (А- + 1,

п) •=

(х +

1) X

ф (х,

л)

X

л

имеем

ф(1,

п ) = 1 Х п Х л

=

/г2,

ф (2,

я) =

2 X

/г2

X

л =

2я3 ,

ф (3,

я) = 3

X

2я3 X п =

6я4

и

вообще

ф (А-,

Л ) =

j t l / i * + ' .

и построить по ней тыорингову

программу

?(ф , исходя

из программ

91/, 5(сг п обычных стандартных

программ.

Для одноместной

функции

ф формула

имеет такой

же вид, как

и в случае итерации,

т. е.

2 "(пока Ф, повторяй ©) с

Выд, с той лишь разницей,

что под

Э следует теперь понимать алгоритм, переводящий тройку

А - || т \\ г

в тройку

х\\т

+

1 || / (т,

г). Для

©

формула будет чуть

сложнее,

чем

раньше, а

именно

Коп »(Е )|S

1 "31/),

где

Коп — копирующий

алгоритм,

перерабатывающий

тройку

х || т || г

в тройку

-v || т \\

т*г.

Аналогично можно рассмотреть примитивно рекурсивную схему

(*) для двуместной (и вообще для многоместной) функции

ср и запи­

сать на входном языке формулу для

программы 2(ф . Если некоторые

можно иногда

придавать

и

«неканонический»

вид,

например:

или

Ф (0,

и) =

g

(л),

ф (л- +

1,

л)

=>

q

(ф

(х,

л))

(« • )

Ф (0,

п ь

л2 ) =

г

(л2 ),

ф (х,

я,,

л2 ) =

q (х,

ф(х,

я 1 :

п2)).

(***)

Приведем несколько таких примеров, когда некоторые из ар­

гументов исходных функций g, jj фиктивны.

Пусть g

(л) =

л, ? ( ( / ) =

1 +

У- Тогда в соответствии со

схемой

ф

(0,

п)

— п,

ф

(дг +

1,

л) =

1 +

ф (-V-,

л)

имеем: ф (1, я)

=

1 +

л, ф (2, я)

•=• 1 +

(1 +

я)

=

2 +

л, ф (3,

л ) =

=

1 +

(2 +

л) •= 3 +

л и вообще ф (х, л) =

х

-+- л. Иначе

говоря,

эта примитивно рекурсивная схема задает сумму, исходя i n функций

п,

I

+

у.

Далее, при g (л) •= 0 и I

(х,

у ,

л) =

у

+

л получаем

схему

Ф (0,

я)

=

0,

ф

(х

+

1,

л) =

ф

(.V,

л) +

л,

определяющую

произведение

л: X

я,

ибо

ф ( I ,

п) =

0 +

я =

я,

ф (2,

я)

=

я

+

п =

2я, ф (3,

я) =

2л +

я

=

Зл и т. д. Если

же

по­

ложить g

(л.) =

1, f; {х, у, п)

=

I / X

а, то получается схема ф (0,

л) =

=

1,

ф (х +

1,

я) =

ф (.t,

я)

X

я,

определяющая

функцию

я*.

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

ф (1,

л) =

1 X

я =

л1 ,

ф (2,

л) =

я ' X п =

я 2 ,

Ф

(3,

л)

=

я 2

X я =

л3 и т. д. Любые «неканонические»

схемы

тако­

го рода

можно

преобразовать

в «канонические» вида «(*), если пред­

варительно осуществить введение фиктивных переменных.

Напри­

мер,

после

реализации

операторов

g

(nlt

пг) = г

(л2 ), I (х,

у , л,,

"г) =

Ё

О*. У)

схема

(***)

принимает

вид

(*).

Поскольку

класс

функций, вычислимых по Тьюрингу, замкнут

относительно

опе­

ратора

введения

фиктивных переменных, то

тем самым

установлена

замкнутость и относительно

примитивных

рекурсий

в

«неканониче­

ской» ситуации, когда в правых частях

соотношений

(*) отсутст­

вуют те или иные аргументы.

Еще

более

общая

ситуация,

чем (*), заключается

в том,

что не­

ном определении.

Например,

для

двух

одноместных функций ф!

и

ф 2

схема

одновременной

(совместной)

примитивной рекурсии

выглядит так:

Ф, (0)

=

сг,

ф, (А-

+

1) =

!л

(х,

Ф,

(х),

ф 2

(*)),

ф 2

(0)

=

С2 ,

ф 2 (х

+

1) =

!«

(X,

ф!

(х),

ф 2

(л:)).

Ф2

В

соответствии

с

этой

схемой

пара

заданных

значений

ф, (0),

(0)

позволяет

вычислить

пару фх (1),

ф 2 (1), а эта

в свою

очередь

пару

ф] (2), ф 2 (2) и т. д. Для

двуместных функций

схема

принимает

вид

<Pi №. л)

=

gl ("). ф] [х +

1, л) =

t-i

(х,

ф,

[х,

п),

ф 2 {х,

л), л),

ф2

(0, я)

=

g, (л), ф; (Л- +

-1, л)

=

£

2 (*,

ф,

(х,

л), ф„ ( Л , я), л)

и аналогично

для любого

числа

функции

от

любого числа пере­

ток, который

при этом получается. При п =

0 деление неосуществи­

мо, но мы доопределим

эти функции, полагая, что они

обращаются

в нуль

при

я =

0.

Допустим, 'что значения

част (х. п)

и ост (х, я)

уже известны. Тогда при переходе к х +

1:

1)

если

ост

(х, я) =

я — 1, то частное увеличится

на единицу,

а остаток обратится

в

нуль;

2)

если

это

не так,

т. е. если ост (х,

л)

< п — 1, то

частное ос­

част (0, я) = 0, част (х

+ 1, л)

= част (х, л)

+ Рв

(ост

(х, я) +

1,

я),

ост (0, л) =» 0, ост (x-\r

1, л) =

(ост (,v, я) +

1)хМн

(ост

(х, л ) +

1,

п).

которой являются /л-мерные векторы

с натуральными координатами.

Построение

соответствующей

тырринговой

программы,

исходя

из

заданных

программ

21

*>(„.,,

SI),,

5l f e

по существу

ничем

не отличается от того, что мы

имеем

для

обычной примитивной

ре­

курсии.

11.4. u-оператор. Примитивная

рекурсия отличается

от

супер-

Позиции и введения

фиктивных

переменных тем, что она существен­

но учитывает специфику

натурального

ряда

— возможность

индук­

тивного перехода от х к х -(- 1. Другое

отличие заключается

в том,

что тыориигово программирование примитивной рекурсии

основано

на повторном (можно сказать — циклическом) применении

исходной

Пусть

I {х,

у) — предикат, т. е. функция, принимающая два значе­

ния: 0

1.. Зададим функцию ф (х) условием: при любом фиксирован­

ном х0

, для

которого существует хотя бы одно значение у такое, что

I (*|>. У) — 1

( т. е. предикат истинный), ф (х„) равно

наименьшему

среди

чисел у таких, что ft (х„, у)

= 1; если же таких у

не существует,

то ф (л-0) не определено. В этом

и заключается применение ц.-опера-

Допустим теперь, что задан

алгоритм 91/, вычисляющий

преди­

кат fsi т. е. распознающий алгоритм,

применимый к парам

х \

\ у и вы­

ясняющий, имеет

ли место свойство 1(х, у) =

1 Естественно,

напра­

шивается

следующий алгоритм

поиска

значения ср (х0 ): проверяем

подряд условие 91/для

пар

х п | | 0 ,

д-01| 1, х0

||

2, ... до тех пор, пока

впервые не будет обнаружено нужное у , если вообще такое у

сущест­

вует; в противном случае процесс

продолжается

неограниченно.

Соответствующая

формула исходного

языка

такова: 2 °

(пока 31/,

повторяй

& | | 5 ) ,

где 2

перерабатывает

х

и х | | 0 . Она

позволяет

строить программу 3|ф ,

коль

скоро

задана 3(/. Аналогично

обстоит

дело, когда ц-оператор применяется

к предикату

ft

(хи

любого числа k +

1 аргументов,

доставляя

функцию;

Ф(х, . . .

xh) =

iiy{f(x1

xk.

у)

=

1).

Допустим, что даны две функции

gx

(хъ ....

х ^ , у) и gj (х,,

х;,, у ) , и имеется у , для которого

(при фиксации

всех

остальных

аргументов) справедливо отношение

=

g^. Пользуясь предикатом

Рв (£, nj, можно это записать так:

Ф ( х ь

... х,,.) =

ц(/(Рв

(gi ( х ъ ...

xh,

у),

g 2 ( x b

..... xh,

(/))=!}

Поскольку суперпозиция, стоящая

в фигурных

скобках,

является

исходя из 9 l P l l ,

9 I g o , то

и 9(ф - может быть

построена. Точно

так же обстоит

дело в случае,

когда вместо fa = fti

рассматривается

отношение fn

< f(i и т. п. Разница лишь в том, что вместо предиката

Рв (|, ц) надо

брать другой двуместный предикат, например Мп (%,

ц) и т. п.

в таком случае обратная

функция х =

ф (у),

очевидно, может

быть

определена посредством

ц-оператора:

ф (у)

их (f, (х) = у ) .

Мно­

утверждать

об обратных

функциях;

например, log с х,

или \f~x~,

вообще говоря, не будет натуральным

числом даже при натуральном

с. В таких

случаях

удобно рассматривать

арифметические

варианты

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

в качестве

значения

функции

объявляется

целая

часть

истинного

значения

функции,

т. е. [ф (у)\. Теперь ясно, что исходя

из функций у = с"

или у => х с

, можно

определить

арифметические

обратные функции

посредством

ц-оператора:

[ log, ( ( / ) ] = цх (/•*+'

> у ) ;

[\/"y]

= lix((x+l)r

>У).