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

понент натуральным числом:

код

(s;).

код (</_,•).

код

(К:) код (Кр).

Это и будет четверка координат конфигурации

/(.

Будем считать, что символы внешнего алфавита и символы со­

стояний занумерованы натуральными

числами S- =

{s0 , s1,

Sr-x),

Q =

{?о. 4\i

Qi' •••> Qh-yi- Соответственно положим

код

(S;-) = (',

код (qj) = /.

Для

дальнейшего

удобно считать,

что

s0

есть

пустой

знак;

итак,

ниже

всюду код (л) =

0.

Символы

s0,

sr_j

можно

во Ki можно

рассматривать как о-ичную запись некоторого

натураль­

ного

числа;

это

и будет код (Ki)-

Например,

для

конфигурации

К

рис.

27,

полагая код

(л)

=

0,

код

(•») =

1,

код

( [ ) =

2.

имеем

(в

троичной

системе

счисления):

код (К;)

==-2 • З 3 +

1 • З 1

+

1 • 3" =

22 =

[211 ] 3 *>.

Что же касается Кр,

то при определении код (Кр)

нам удобно интер­

претировать

Кр как число, записанное «зеркально», т. е. старшие раз­

ряды записаны правее младших. Например, для

конфигурации

К

рис.

27

имеем

код

(Кр)

=

1,3°

+ 0,3" + 2-3? =

19 =

[201]3 .

Итак,

для

конфигурации

К имеем: s = 2,

9 = 3 ,

т=

22,

п=

19.

На рис. 27 изображена также конфигурация К',

получаемая

из

К

применением

команды

| qs

-*• »I7q2 .

Для нее s'

=

1, q' =

2,

tn'

=

=

68, п'

=

6.

Теперь

покажем, что s',

q',

/и', п'

как

функции

от s,

q,

т,

п

примитивно

рекурсивны.

Ранее

мы

уже

закодировали

внешние

символы

и

состояния

числами. Закодируем еще и сдвиги:

Г — с д в и г

вправо,

2 — сдвиг

влево, 0 — отсутствие

сдвига. Тогда

функциональная

схема

маши­

ны Ш задается посредством тройки функций S (s, q),

Р (s, q),

Q (s,

q),

которые по кодам s, q входной пары вырабатывают

соответственно

коды переработанного символа, сдвига и

нового

состояния.

Эти

функции

определены

только при s

<

г и q <

k,

но, доопределяя

их

сивны. Вернемся теперь к интересующим нас функциям s'

(s, q,

т,

п),

q' (s, q, tn, n),

m'

(s, q, tn, n) и n'

(s,

q,

tn,

n).

Примитивная

рекурсивность

функций s'

и q'

очевидна,

ибо

s'

(s, q, m, n)

=

S

(s,

q), q' (s,

q,

tn,

n) =

Q (s,

q). Что же касается

функций

т ' и

п',

то мы рассмотрим в отдельности три случая

в зави­

симости

от того,

какой сдвиг

произошел

при

переходе

от

К к

/ ( ' .

1. Отсутствие сдвига, т. е. Р

(s,

q) =

0. Тогда

tn' =

т,

п'

=

п.

2.

Сдвиг

вправо,

т. е. Р (s, q) =

1. Тогда

левое крыло Ki раз­

растается вправо

и,

захватывая

s',

образует

Ki,

Поэтому

т'

=

=

код (K'i) =

rn-r

+

s'. Правое же крыло Кр укорачивается,

отсту­

пая из

самой

левой ячейки, в которой

записан

младший

разряд чис­

ла п. Поэтому

п' => паст (п, г).

3.

Сдвиг

влево, т. е. Р (s, q) =

2.

Аналогично

проверяется,

что

т'

=

част (т.

г),

п' = n-r +

s'.

т ' =

p B (P(s,

q),

0)-т

+ Рв (Р (s, q),

l)-(m-r + s')

+

+

Рв (Р (s.

1/),

2)

-част (//г, л)|

п ' =

Р в ( Р ( 5 .

q),

0)-и

+

P

B ( P

( S ,

q),

1)част(п, /•)+

+

Рв ( P ( s ,

q),

2)(п-

+.s')-

Итак, функции т'

(s,

q, т, п) и п'

(s,

q,

in, п) представлены посредст­

вом суперпозиций

примитивно

рекурсивных функций Рв, Р, s'

(она же S), част, + ,

X . Следовательно, они

примитивно

рекурсивны.

Тем самым корректность

предложенной коордииатизацни пол­

сывающих

работу машины

Тьюринга. Пусть

машина

Ш запущена

в некоторой

конфигурации

/( с координатами s,

q, in, п.

Тогда после

таем,

что

/<° =

К).

Координаты

конфигурации

/ ( ' , естественно,

зависят от координат исходной конфигурации

/( и от t,

т. е. являют­

ся функциями от пяти аргументов: t, s, q,

in, n; обозначим их S, Q,

M,

N-

Легко видеть,

что эта

четверка функций

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

одно­

временной

примитивной

рекурсией,

исходя

из

функций s',q',

in',

п',

а следовательно,

все

они

тоже

примитивно рекурсивны. Дейст­

вительно,

S (0, 5 ' ,

q,

т,

п)

=

s,

Q (0,

s,

q,

in,

п)

=

q;

М

(О, s,

q,

in,

п)

«=

m,

/V (0,

s,

q,

in,

n)

•=

n;

S

(t+

\,s,q.

in,

n) =

s'

(5

(/, s, q,

m, n),

Q

(I, s, q, in,

л),

M

(I, s, q.

m,

n),

N

(t, s,

q,

in,

n));

Q

(t +

1,

s,

q, in,

n) =

q'

(S

(I,

s,

q, in,

n),

Q (t, s,

q,

m, n), M

(I,

s,

q,

in,

n), N

(I,

s,

q,

m,

n));

M

(I

+

1,

s,

q,

m,

n)

=

m' (S

(I,

s,

q, in,

n),

Q

(t,

s,

q,

in,

n),

M

(I,

s,

q,

m,

n)

N

(t,

s,

q,

in,

n));

N

(t

+

1,

s,

q,

m,

n)

=

n'

(S

(I,

s,

q,

ill, n),

Q

(I,

s,

q,

m,

n),

M

[t,

s,

q,

in,

n),

N

(I, s,

q,

in,

n)).

палочки,

а

еще одна палочка обозревается головкой

в

начальном

состоянии

qx

(см. рис. 27). Следовательно, код

(Кр)

=

(г— l ) r v ~ 2

+

+

(г — 1)гх~3

+ ...

+

(г — 1)л° =

г * - 1

—

1,

а

четверка

коор­

динат конфигурации

Кр

такова: г —

I ,

1, 0,

г 1 " - '

— 1.

Поэтому при варьировании начальной конфигурации с унарной

записью аргумента х координатные функции S,

Q, М,

N

становятся

функциями

от

двух

переменных

I,

х.

Введем

для

них

обозначения

S,

Q, М,

N,

т. е.. S (1, х)

=

S (t,

г —

1,

1. О,

г*"1 —J ) ,

Q

х)

=

<= Q (/,/•— 1,

1, 0,

г * - 1

—

1) и т.д_. Очевидно,

S, Q, М, 7V тоже

при­

митивно-рекурсивные функции. Пусть стоп-состояипе

закодировано

расходует машина fflj при вычислении значения I (х),

может быть вы-,

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

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

исходя

из Q:

T

( X ) = U * (

Q

[I. x)

=

k),

а следовательно, тоже

является

рекурсивной.

Далее,

рекурсивная функция

Л/(т(х),

x) = N{%(x),

г — 1,

1,

0, л * - 1

_ 1)

в точности

задает

л-координату

заключительной

конфигурации

(см.

рис.

27),

которая

равна

— 1. Значит,

окончательно

для

функции

f/ (х)

получается

представление:

/(х) =

1 +

logr

[iV (т (х)

1, 0,

^ - 1 — 1 ) + 1 ] .

Этим и завершается

рекурсивное описание

функции

I (х).

§ 12. ВАРИАНТЫ ВНЕШНЕЙ ПАМЯТИ

Правильное течение любого вычислительного процесса обеспечи­

вается тем, что

на каждой его стадии в памяти (машины или

вычис­

лителя) сохраняются

те данные,

которые могут понадобиться

набо­

лев поздних стадиях. Такие данные не только

не могут быть искаже­

ны

или стерты

раньше времени,

но и должны размещаться достаточ­

но удобно в памяти,

чтобы их можно было отыскать и

использовать

в нужный момент. В реальных

вычислительных

машинах это,

как

известно,

достигается

засылкой

промежуточных

результатов

в

спе­

циальные устройства

— регистры машины или в ячейки

памяти с из­

вестными

адресами,

где они хранятся вплоть до того момента,

когда

ринга. В качестве следствия мы

получим доказательство теоремы

о программировании параллельной

композиции, сформулированной

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

вать некоторые разновидности тыоринговой

машины,

отличающие­

ся от ранее изученного основного образца

лишь

особенностями

внешней памяти, т. е. ленты. Сначала рассмотрим машину 'Ш с пра­

вой полулентой (рис. 28,

о), бесконечной только в одну сторону —

а именно вправо. Можно

считать, что ячейки ленты занумерованы

в)

II

X

X

У

У

X

А

1

?

г)

II

X

X

У

У

X

Ч

д-

1

з)

Н

X

У

У

X

Д

ег

и

X

X

У

У

X

д

7.

3

Z

/

О

ж) Pit)

ЦЪ-2)

Pto)

II

р,

Рис.

28.

нение имеют такой же вид, как

обычно,

с единственной

оговоркой:

в каком бы состоянии машина

ни обозревала

знак

|| , команда

предусматривает

сдвиг

вправо

без изменения

символа || . Иначе

во Р =

Р

(\)Р

(2) ... Р

(v)

(см. рис.

28, а) записано на краю полу­

ленты,

т.

е. в

ячейках

с

номерами

1, 2,

тогда

фактически

весь процесс вычисления

происходит правее знака || , и он

может за­

кончиться

выдачей некоторого результата

R = R (\)R

(2) ...R (s),

оговорок

мы,

как и

прежде, будем применять обозначение вида

Ш (Р) =

R и считать,

что начальная

и заключительная

конфигура­

ции стандартны, т. е. что обозревается

первый

символ слова (не счи­

тая символа ||

из нулевой ячейки). Аналогично определяется машина

с левой

полулентой.

Обозначение Ю? (Я) =

R будет

применяться

его

символ.

Результат — слово

R — записан

где-то левее символа

|| и

в нем

также обозревается

первый слева

символ. Совершенно

па 93с. Тогда Ш является последовательной

композицией

трех

схем:

9i =

91 ° Ш 0

2,

где 3( переводит

слово

Я в слово

|| Я

и возвра­

щает

головку

к первой букве

слова

Я, 2

отыскивает

символ

|| ле­

вее результата

R,

стирает его

и* возвращает

головку к первому

сим­

Справедливы

следующие

утверждения.

Т е о р е м а

1.

Существует

программирующий

алгоритм,

ко­

торый

любую

тыорингову

программу

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

в

программу

(|| 9!)

для

машины

с правой

полулентой;

при

этом

выполняются

условия:

a)

91 (Р) •= R тогда

и

только

тогда,

когда

(Ц91)

(Я)

=

R;

б) в машине

|| 91

результат

R

(так

же, как

и

Р)

записан

на

краю

полуленты.

строится

2.

Т е о р е м а

2 формулируется

аналогично;

по 91

программа

(91 || )

для

машины

с левой

полулентой.

Прежде чем привести соответствующие доказательства,

пока­

жем, как из этих теорем выводится теорема о программировании

па­

раллельной композиции

'JI, || %2

двух

алгоритмов

?lj

я[2

Сначала

строим

программы

91, ||

и

|| 912 . Затем

формируем

9t, || >}12

как

ком­

позицию

следующих

четырех

программ:

1)

||)

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

Я, || Я 2

в

31г

(Я,) ||

Я 2 ;

2) 2, перемещает головку с первой

буквы

слова

"Л, (Ях )

к

пер­

вой букве

слова

Я 2 ;

3)

(II 312)

продолжает

переработку

до

выдачи

слова

'JIj (Рг) ||

11ч-'г (^г)•

причем

головка

обозревает

первую

букву

из

912

(Я2 );

4)

£ 2

перемещает головку

с

первой

буквы

$[2

(Я2 )

к

первой

букве

2d

(Pi).

Построение

стандартных

программ

£ 2

тривиально, и мы его

здесь

опускаем'.

У п р а ж н е н и е .

Описать

программирующий

алгоритм

для'

параллельной композиции трех или более программ.

12.2.

Доказательство

теоремы

о

полуленте.

Перейдем

теперь

к доказательству

теорем

1 и 2. Для

определенности

рассмотрим

слу­

чай с правой

полулентой. Программа

(ЦЭ1)

строится

как

последо­

вательная

композиция трех программ:

"21»97"8,

из

которых

основ­

ную нагрузку несет

91,

в

то

время

как

21, 2

— две

стандартные

программы, не зависящие

от

исходной

программы

91 и

выполняю­