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

Рассмотрим

некоторую конфигурацию машины Тьюринга. Усло­

вимся

называть

активными

в данной конфигурации

следующие

ячейки:

а)

обозреваемую ячейку,

б)

ячейки,

заполненные

буквами (отличными от

пустого

зна­

ка

л ) ;

в)

всякую ячейку, левее и правее которой имеются

ячейки

типа

а)

или

б).

ты — ее активную часть. На рис. 33 изображены

некоторые конфи­

гурации и отмечены соответствующие

активные части ленты. В кон­

фигурации рис. 33, ал обозреваемая

ячейка не

является крайней,

to

Ь

5

)

a)

'

}ПТ~к1 \3\QL\

\\

\\

I N

1 Г II

6)

e)

Рис.-33.

т. е. левее и правее ее все еще имеются ячейки активной

части ленты.

Такую конфигурацию будем называть глубинной

в отличие от конфи­

гураций типа рис. 33, б,

в, г, которые будем называть

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

но левой, правой,

одиночной.

su

st,

Предположим,

что внешний

алфавит машины

такой;

sm , а внутренний алфавит такой: qx,

q2

q^.

Введем еще в рассмотрение букву h (не входящую в указанные

алфавиты) и предназначенную для обозначения краев активной

части

лепты.

hRh,

Всякую конфигурацию можно обозначить в

виде

слова

где R—слово,

составленное так,

как это было

сделано

в п. 14.2. Эти

слова будем называть /(-словами (конфигурационными).

Например,

конфигурациям рис. 33 соответствуют слова

Л I Л а

Л

<?о РаЛ;

Л | q0 Д

а

Д

h | Д а Д

р а Д q0h\'

haq0h.

Сопоставим теперь машине

М исчисление

пм

следующим

обра­

зом :

1. Алфавит пм

состоит из буквы h и всех букв алфавитов

маши­

ны М. Заметим, что в то время,

как всякое

/(-слово является словом

в исчислении

п Л ) , не всякое слово в пм

является конфигурационным.

Так, например, в слове

hs^^q^i

дважды

встречается

внутренняя

буква gj, чего не может быть в /(-слове.

2. Подстановки

(ориентированные)

в лм

строятся так, чтобы они

обеспечивали

в точности такие преобразования

/(-слов, которые соот­

ветствуют преобразованиям конфигураций

в машине согласно ее ко­

мандам. Пояснимподробнее, как это

делается.

Рассмотрим команду вида

sq + s'Hq',

(1)

няется. Если

сравнить /<-слова до и после применения команды, то

оказывается,

что

пара

букв sq

просто заменяется парой букв s'q'.

В соответствии с этим

команде

(1)

машины Тьюринга сопоставляем

в исчислении

пм

ориентированную

подстановку

sq -*

s'q'.

h

Ь

h

Ь

U ' I ' M i

к

? 2

г)

о.)

б)

в)

Рис. 34.

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

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

ориентированной

подстановки, которая

была бы ей

равноценна

(в том смысле, как это было сделано для команды (1)).

Однако, как

будет показано ниже, можно указать конечную систему

подстановок,

которая в своей

совокупности равноценна данной

команде.

П р и м е р .

В соответствии с командой | q„ -*

л / 7 ? 2 из функ­

Для соответствующих /(-слов

имеем преобразования, представ­

ленные табл. 3.

Т а б л и ц а 3

Иоходное К-слово

Преобразованное

/(-слово

Л II <?,, 1 л

h \ Л

I

q2 h

h\q0\h

h 1 g2

h

h || q0 ft

h | Л Л q2

h

h\q,h

ft A

<72 ft

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

что слова из

правого столбца не возникают

за

счет применения

одной

и

той

же

ориентированной

подстановки

к соответствующим

словам

из левого

столбца.

Покажем теперь, как строится система ориентированных

под­

становок

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

команде

вида

sq-+s'nq',

(2)

(Случай

команды

вида

sq -*• s'JIq'

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

аналогично).

Введем следующие обозначения: если ячейка,

примыкающая

слева к обозреваемой, является

активной,

то букву,

помещенную

в ней, обозначим

через о; аналогично, т обозначает букву,

помещен­

ную в соседней

ячейке

справа,

если она

активна;

при

этом

не

исключено, что о или'Ъ. или обе одновременно — пустые энаки.

Подстановки, соответствующие команде (2), удобно классифи­

цировать

по типам

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

I ч-

шли

I

ч

I

h

п

!

*

[ Ж С Б

г п ~ п

Рис 35.

Рис. 36.

Рис.

37.

1. Глубинная

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

В /(-слове

имеются

вхождения

вида asqt.

Каждому

такому

вхождению (о, т — произвольные

внеш­

ние

буквы

машины)

соответствует

подстановка asqx-*

as'xq'.

2. Левая конфигурация. В /(-словах имеются вхождения вида

hsqx. Им соответствуют подстановки вида

hsqx -* hs'

<zq',

если

s'

ф

Д

hsqx -t hxq',

если

s'

— Д .

Последняя

подстановка отражает тот факт, что ячейка, содержавшая

s, перестает быть

активной (см. рис. 35)

3. Правая конфигурация. В /(-словах имеются вхождения вида

csqh,

которым

соответствуют

подстановки

asqh -»• as' л q'li,

отра­

жающие факт

удлинения справа активной части ленты (см. рис. 36).

4. Одиночная конфигурация. В /(-словах

имеются

вхождения

hsqh,

которым

соответствуют

подстановки

hsqh -+ hs'

Д q'h,

если

s'

ФА.

hsqh-* h Д

r/'Л,

если

s'

=

Д .