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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

14
(6)
L
b
a
b
b
L
3
q
(7)
L
b
a
b
b
b
0
q
Более короткая запись этой последовательности конфигураций, т. е. про-
цесса работы машины будет
Þ
L
Þ
L
Þ
L
Þ
bbbaqabbbqbabbqbbabbq
3331
.
33
babbbbabbqbbabq
Þ
L
L
Þ
L
Þ
Таким образом, слово
bbabb
переработано машиной в слово
babbb
.
Пример 3. Задается машина Тьюринга внешним алфави-
том
}
{
c
b
a
A
=
, алфавитом внутренних состояний },,,{
3210
qqqqQ
=
и
программой:
,
11
Лaqaq
®
,
32
Пbqaq
®
,
13
Лaqaq
®
,
21
Лaqbq
®
,
22
Лbqbq
®
,
33
Пbqbq
®
,
01
aqcq
®
,
22
Лcqcq
®
,
22
Haqq
®
L
.
33
Пcqcq
®
Заметим, что программа этой машины может быть записана в виде сле-
дующей таблицы:
1
q
2
q
3
q
a
Лaq
1
Пbq
3
Лaq
1
b
Лaq
2
Лbq
2
Пbq
3
c
aq
0
Лcq
2
Пcq
3
Для того чтобы определить по таблице, что будет делать машина, нахо-
дясь, например, в состоянии
2
q и наблюдая в обозреваемой ячейке символ
b, нужно найти в таблице клетку, находящуюся на пересечении столбца
2
q
и строки b. В этой клетке записано bЛq
2
. Это означает, что на следующем 
    (6)                     �         b           a         b     b       �

                                                                          q3

    (7)                     �         b           a         b     b       b

                                                                          q0


Более короткая запись этой последовательности конфигураций, т. е. про-
цесса работы машины будет

                   q1bbabb � �q 3 babb � �bq 3 abb � �baq 3 bb �

                           � �babq 3 b � �babbq 3 � � babbb.

       Таким образом, слово bbabb переработано машиной в слово babbb .

       Пример         3.   Задается        машина      Тьюринга       внешним   алфави-
том A � {a, b, c} ,    алфавитом внутренних состояний Q � {q0 , q1 , q 2 , q3 } и
программой:

      q1a � q1 Лa, q2 a � q3 Пb, q3a � q1 Лa, q1b � q2 Лa, q2b � q2 Лb,
          q3b � q3 Пb, q1 c � q 0 a, q2c � q2 Лc, q 2 � � q 2 Ha, q3c � q3 Пc.

Заметим, что программа этой машины может быть записана в виде сле-
дующей таблицы:

                                          q1           q2        q3
                            a         q1 Лa           q3 Пb     q1Лa
                            b         q2 Лa           q 2 Лb    q3 Пb
                            c             q0 a        q2 Лc     q3 Пc


Для того чтобы определить по таблице, что будет делать машина, нахо-
дясь, например, в состоянии q 2 и наблюдая в обозреваемой ячейке символ
b, нужно найти в таблице клетку, находящуюся на пересечении столбца q 2
и строки b. В этой клетке записано q 2 bЛ . Это означает, что на следующем
                                                 14

Страницы