Составители:
109
Теперь неформально опишем универсальную машину Тьюринга (U). Вход в
неё, как сказано, устроен на двух-дорожечной ленте. Нижняя дорожка будет
содержать кодировку некоторой машины Тьюринга (T), за которой будет
следовать цепочка из нулей и единиц, представляющая её входные данные.
Данные отделяются от кодирования машины тремя последовательными с.
Первоначально верхняя дорожка будет вся заполнена символами B, за
исключением двух ячеек: третьего символа с в цепочке ссс в начале кода
машины и первой ячейки данных — см. ниже:
m m
ccc блок сост. 1 cc блок сост. 2 cc ... cc блок последнего состояния ссс 0110...
Универсальная машина Тьюринга U будет моделировать движения,
которые бы предпринимала Tm T на входной цепочке, представленной как
данные на ленте машины U, следующим образом.
Во-первых, машина U передвигает свою головку вправо, пока она не
обнаружит маркер в области данных над входным символом, сканируемым
машиной T. Этот символ, назовем его A, запоминается в конечном управлении
машины U, которая с этого момента начинает движение влево, пока не
достигнет маркера, регистрирующего текущее состояние машины T
(отмечающего соответствующий блок в коде таблицы машины T). Машина U
удаляет этот маркер (заменяет его символом B), передвигается вправо к
подблоку, соответствующему символу A, и помещает маркер над первым
символом в этом подблоке при условии, что он есть 1. Если же он — 0, то
машина U останавливается, поскольку никакого следующего движения маши-
ны T не определено. В последующем этот маркер подблока будем называть m
1
.
Предположим, что первый символ был 1. Тогда машина U движется влево,
пока не находит цепочку ссс. Затем машина U движется вправо, помечая
крайнее правое из этих трёх с. Этот маркер назовем m
2
. Машина U продолжает
продвигаться вправо, пока не найден маркер m
1
. После этого машина U входит
в подпрограмму, которая попеременно передвигает маркер m
1
на одну 1 вправо,
а маркер m
2
—
на один блок вправо. Чтобы отличить маркеры, которые оба есть
m, машина U будет запоминать в своем конечном управлении, какой маркер
она видела последним. Когда машина U сдвигает m
1
на символ, который не
является 1, маркер m
2
располагается над символом с, который как раз перед
блоком, соответствующим следующему состоянию машины T. В этой точке
машина U удаляет маркер m
1
и записывает в своем конечном управлении
символ, который машина T будет печатать, и направление, в котором машина T
будет двигать свою головку ленты. Затем машина U снова движется вправо в
область данных и находит маркер, который указывает место головки ленты
машины T. Символ, находящийся под маркером, заменяется на символ,
запомненный в конечном управлении, а маркер сдвигается на одну ячейку в
направлении, также зафиксированном в конечном управлении. Таким образом,
машина U смоделировала одно движение машины T.
Далее машина U запоминает новый символ, сканируемый машиной T, в
своем конечном управлении, начинает двигаться влево, пока не достигнет
маркера m
2
, регистрирующего состояние машины T, и повторяет процесс,
который был только что описан.
данные
Страницы
- « первая
- ‹ предыдущая
- …
- 108
- 109
- 110
- 111
- 112
- …
- следующая ›
- последняя »
