Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 8 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

8
ровно одну ячейку ленты. Головка может считывать содержимое ячейки и
записывать в нее новый символ из алфавита А. В одном такте работы она
может сдвигаться только на одну ячейку вправо (П), влево (Л) или оста-
ваться на месте (Н). Обозначим множество перемещений (сдвига) головки
D = {П, Л, Н}. Если в данный момент времени
t
головка находится в край-
ней клетке и сдвигается в отсутствующую клетку, то пристраивается новая
пустая клетка, над которой окажется головка в момент
1
+
t
.
3. Внутренняя память машины представляет собой некоторое конеч-
ное множество внутренних состояний
Q
= {
0
q ,
1
q ,
2
q , ...,
m
q },
1
³
m
. Бу-
дем считать, что мощность |
Q
| ³ 2. Два состояния машины имеют особое
значение:
1
q – начальное внутреннее состояние (начальных внутренних
состояний может быть несколько),
0
q – заключительное состояние или
стоп-состояние (заключительное состояние всегда одно). В каждый момент
времени МТ характеризуется положением головки и внутренним состоя-
нием. Например, под ячейкой, над которой находится головка, указывается
внутреннее состояние машины.
¯
2
a
1
a
L
2
a
3
a
1
q
4. Устройство управления в каждый момент t в зависимости от счи-
тываемого в этот момент символа на ленте и внутреннего состояния ма-
шины выполняет следующие действия: 1) изменяет считываемый в момент
t символ
i
a на новый символ
j
a (в частности оставляет его без изменений,
т. е.
ji
aa
=
); 2) передвигает головку в одном из следующих направлений:
Н, Л, П; 3) изменяет имеющееся в момент t внутреннее состояние машины 
ровно одну ячейку ленты. Головка может считывать содержимое ячейки и
записывать в нее новый символ из алфавита А. В одном такте работы она
может сдвигаться только на одну ячейку вправо (П), влево (Л) или оста-
ваться на месте (Н). Обозначим множество перемещений (сдвига) головки
D = {П, Л, Н}. Если в данный момент времени t головка находится в край-
ней клетке и сдвигается в отсутствующую клетку, то пристраивается новая
пустая клетка, над которой окажется головка в момент t � 1 .
      3. Внутренняя память машины представляет собой некоторое конеч-
ное множество внутренних состояний Q = { q0 , q1 , q 2 , ..., q m }, m � 1 . Бу-

дем считать, что мощность | Q | � 2. Два состояния машины имеют особое
значение: q1 – начальное внутреннее состояние (начальных внутренних
состояний может быть несколько), q0 – заключительное состояние или
стоп-состояние (заключительное состояние всегда одно). В каждый момент
времени МТ характеризуется положением головки и внутренним состоя-
нием. Например, под ячейкой, над которой находится головка, указывается
внутреннее состояние машины.


                  �

                  a2      a1       �       a2      a3

                  q1


      4. Устройство управления в каждый момент t в зависимости от счи-
тываемого в этот момент символа на ленте и внутреннего состояния ма-
шины выполняет следующие действия: 1) изменяет считываемый в момент
t символ ai на новый символ a j (в частности оставляет его без изменений,

т. е. ai � a j ); 2) передвигает головку в одном из следующих направлений:

Н, Л, П; 3) изменяет имеющееся в момент t внутреннее состояние машины
                                       8

Страницы