Математическая логика и теория алгоритмов. Галуев Г.А. - 51 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 51 из 64
© 2003 Галуев Геннадий Анатольевич
Конфигурация однозначно определяет работу МТ. Пусть
β
α
,
- конфигурации
некоторой МТ z, а Р,R- произвольные последовательности символов на ленте. МТ пе-
реходит из
α
в
β
()
β
α
→ в одном из трех случаев
1. по команде
jlki
qxxq
. В этом случае символ
k
x в рабочей ячейке заменяется
l
x , состояние
i
q заменяется состоянием
j
q , а лента остается без движения
RxPq
ki
=
α
, xlRPq
j
=
β
2. по команде
jki
lqxq
. Лента передвигается на одну ячейку влево, состояние
q
меняется на
j
q , RxPq
ki
=
α
, RqP
j
i
k
x
=
β
.
3. по команде
jki
rqxq . Лента передвигается на одну ячейку вправо, состояние
i
q заменяется на
j
q
,
xlRqPx
jk
=
α
,
xlRxPq
kj
=
β
Конфигурация
α
называется заключительной, если не существует такой кон-
фигурации
β
, что
β
α
→
.
Вычислением в МТ называется последовательность
конфигураций l,,...,,
γ
β
α
,
таких что
β
α
→
,…,
l→
γ
, где l - заключительная конфигурация.
Анализ и синтез машин Тьюринга
Проблема анализа МТ состоит в том, чтобы для данной МТ определить на каждом
шаге её реакцию на заданное входное слово т.е. в построении вычисления в МТ. Про-
ведем такой анализ на примере конкретной МТ.
Например: Пусть МТ задана таблицей Тьюринга
1.
000
lqxq 5.
001
lqxq
2.
020
lqxq 6.
021
lqxq
3.
110
lqxq 7.
2212
qxxq
4.
211
rqxq
Заметим, что эту же МТ можно задать с помощью таблиц Айзермана
XQ\
0
x
1
x
2
x
XQ\
0
x
1
x
2
x
XQ\
0
x
1
x
2
x
0
q
0
q
1
q
0
q
0
q
0
x
1
x
2
x
0
q
l
l
l
:
δ
1
q
0
q
2
q
0
q
:
μ
1
q
0
x
1
x
2
x
:
λ
1
q
l
l
2
q
-
2
q
-
2
q
-
2
x
-
2
q
-
S
-
Табл. 4
Или обобщенной таблицей
XQ\
0
x
1
x
2
x
0
q lxq
00
lxq
11
lxq
20
1
q
lxq
01
rxq
11
lxq
21
2
q
-
sxq
22
Табл. 5
Пусть на ленте записано входное слово
1011201
xxxxxxx и МТ находится в началь-
ном состоянии
0
q , а головка находится против самого левого символа входного слова
(т.е. против
1
x ). Процесс анализа (т.е. процесс вычисления) записывается следующи-
ми конфигурациями:

Страницы