Составители:
Рубрика:
непосредственно со специфическими особенностями
вычислительных машин.
4.2. Машина Тьюринга
Модель алгоритма, называемая машиной Тьюринга [16],
состоит из бесконечной ленты (БЛ), разделенной на ячейки, и
управляющей головки (УГ), которая перемещается по ленте и
способна считывать символ в
ячейке, против которой она
находится, а также замещать
обозреваемый символ новым
(рис.4.1).
В каждой ячейке может
быть записан один символов из ленточного алфавита A. Головка
может находиться в одном из внутренних состояний,
принадлежащих конечному множеству (алфавиту состояний) Q.
Работа машины происходит в дискретном времени в соответствии с
программой, задаваемой набором команд вида
БЛ
УГ
Рис.4.1.
+ +
qa → a
Dq .
В зависимости от состояния головки q∈Q и символа a∈A,
против которого она стоит, головка записывает на ленте новый
символ a
+ +
(или оставляет старый), переходит в новое состояние q
(или остается в старом) и передвигается: вправо (П), влево (Л) или
остается в прежнем положении (Н).
Назовем конфигурацией машины Тьюринга K
t
в момент t
содержимое ее ленты, состояние головки q∈Q и обозреваемый ею
символ a. Пусть на ленте записана цепочка символов
…Λa
a a a a a
1 3 1 2 3 1
Λ…, слева и справа от которой свободные ячейки
(содержат символ Λ), причем головка, находясь в состоянии q
i
,
обозревает символ a
2
. Соответствующую конфигурацию будем
записывать, помещая обозначение состояния головки перед
обозреваемым символом: a
a a q
1 3 1 i
a a a .
2 3 1
144
Страницы
- « первая
- ‹ предыдущая
- …
- 58
- 59
- 60
- 61
- 62
- …
- следующая ›
- последняя »
