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

Команды

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

0(72010

0^110

<730д4П

01<7,10-*011?,0

OlfclO

01? 5 00

0<7в100

с?в0Ю0

qa0q00C

%0100

Как

было уже сказано, на машинах

Тьюринга оказалось

воз­

можным

осуществить или имитировать

все алгоритмические

про­

о существовании или несуществовании машины Тьюринга,

облада­

ющей нужным свойством.

В зависимости от числа используемых

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

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

различные

модификации машин Тьюринга. Рассмотрим

основные из них.

1.3.2. Машины Тьюринга с двумя выходами

Предположим, мы расширили

определение машины

Тьюринга,

добавив в устройство управления

машины

определенное

состоя­

ние q*. Будем говорить,

что если

устройство

управления

перехо­

дит в состояние qo для

заданного

входного

слова х,

то машина

допускает х. Если устройство управления

приходит в состояние q *,

ной Тьюринга с двумя

выходами.

Тьюринга 7\ и Т2,

Оказывается, что если заданы две

машины

которые допускают непересекающиеся

множества слов Xi и Х2 соот­

ветственно, то всегда

можно построить машину Тьюринга Ts с дву­

мя выходами, которая

будет допускать Xt и запрещать Х2. Эти ма­

шины Тьюринга

будут нам полезны при рассмотрении

вопроса о

разрешимости.

Множество

разрешимо,

если

существует

машина

Тьюринга

с двумя выходами, которая

допускает все элементы

этого множе­

ства и запрещает элементы, не принадлежащие ему.

1.3.3. Многоленточная машина Тьюринга

Схема многоленточной

машины

Тьюринга

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

рис. 6. Она состоит из некоторого

конечного

числа

лент,

разбитых

на ячейки. В каждой ячейке

может находиться

один из символов

внешнего алфавита А

— {s0,

su ...,

sn}.

Ячейки

с символом s0 бу-

ний Q = {#о, Яи • • •,

Ят}- Состояние q0 считается

заключительным

состоянием

машины.

Предположим, что в каждый

момент времени машина «обозрева­

ет» одну ячейку каждой ленты,

о.

Конфигурация машины счи-

r—i—I—г—|—I—1^|

I—I—|—]—I—?

тается заданной,

если

известно

? 1 1

1

1 1

1 I

I I

I I

I

! состояние устройства управле­

[ s„\

ния

я, состояния

всех

ячеек

|

|

I

]

.[

~ ~ j

всех

лент

и указаны

ячейки,

' '

—|—.—j—7

воспринимаемые машиной. Для

fe-ленточной

машины

конфигу-

\

I se [

I 1 }

рация

ее в г'-й момент

Р и с 6

описывается системой А-слов

вида:

Sill

• • • SileQiStte+\ • • • snt>

(9)

по одному слову для каждой ленты первый

индекс

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

моменту

времени, второй — номеру

ленты, третий — номеру

ячейки

на ленте, считая слева направо.

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

устройства

управле­

ния Яг содержимого

обозреваемых в данный

момент

ячеек

лент

Siie+i • •. Sike+i' машина

переходит в следующее

состояние

посредст­

вом таких

действий:

1) состояние каждой воспринимаемой ячейки заменяется новым

состоянием

(которое может

совпадать

со старым);

2) каждая лента передвигается на одну

ячейку

вправо,

влево

или остается неподвижной;

q% переводится

3)

внутреннее состояние

устройства

управления

в новое состояние Яз (которое может совпадать со старым).

Считается, что если устройство

управления

в какой-то

момент

приходит

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

состояние

qo, то машина

останавли­

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

машины не

меняется.

Говорят, что машина выполняет

команду

ЯМ

. . . s^-^q^T,

. . . s-,kTk,

Т =

{Л, С, П},

(10)

щие буквам внутреннего алфавита и буквам внешнего

алфавита.

Рассмотрим пример такого кодирования для

машины Тьюрин­

га Т, имеющей внешний алфавит А =

{su s2, . . . ,

sf t }

и

внутренний

алфавит Q = {qb q2,...,

qm) •

Тьюринга сос­

Если внешний алфавит универсальной машины

тоит из символов А =

{0, 1}, то эти

условия

будут

наверняка

соблюдены при следующем способе кодирования.

Буква

Кодовая группа

Л

101

с

1001

п

10001

Внешний

100001—4

нуля

Четное

10000001—6

нулей

число

алфавит

S2

нулей,

sK

10 1 .' .' 01 2(к-Н)

большее

нулей

чем 2

1000001—5

нулей

Нечетное

Внутренний

92

100000001—7

нулей

число

алфавит

нулей,

(состояния)

10;

. 01 2 ( / и + 1 ) + 1

большее

нулей '

чем 3

ва bcadc в слово bcdcc, входное

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

машине

Тьюринга с данным кодом будет представлено следующей

строкой:

10000001 1000000001 100001

100000000001 1000000001,

где 100001 — а, 10000001 — Ь, 1000000001 — с, 100000000001 — d.

Программа же будет представлена

следующими

строками:

1000001 10000001 1000001 10000001

101

(цфцфЛ)

1000001 1000000001 1000001 1000000001 101 (<7оС?осЛ)

1000001 100001 100000001 100001 101 [q^aqioR)

(qid2q2cU)

100000001 100000000001 10000000001

1000000001 10001

10000000001 100001 100000000000001

100000000001 10001

(d2aqudTl)

Если же алгоритм,

реализуемый

машиной

Tnj не применим

к слову хп, то алгоритм,

реализуемый

универсальной машиной Ти,

также не применим к слову,

образованному из изображения хп и

программы машины Тп.

Тп может

Таким образом, машина

Тьюринга

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

как одна из программ для универсальной машины

Ти.