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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

13
Эта конфигурация является заключительной, так как машина оказалась в
состоянии остановки
0
q .
Таким образом, слово
ba
переработано в слово
ab
.
Полученную последовательность конфигураций можно записать более
коротким способом. Конфигурация (1) записывается в виде следующего слова
в алфавите
Q
A
È
: baq
1
(содержимое обозреваемой ячейки записано справа от
состояния, в котором находится данный момент машина). Далее, конфигура-
ция (2) записывается так: aq
3
, конфигурация (3) –
L
3
aq , и наконец, (4) –
0
abq .
Вся последовательность записывается так: .
0331
abqaqaqbaq
Þ
L
Þ
L
Þ
Пример 2. Применить машину Тьюринга
1
T из примера 1 к слову
bbabb, исходя из начального положения, при котором в состоянии
1
q обо-
зревается крайняя левая ячейка, в котором содержится символ этого слова.
Решение
(1)
b
b
b
b
1
q
(2)
L
b
b
b
3
q
(3)
L
b
b
b
3
q
(4)
L
b
b
b
3
q
(5)
L
b
b
b
3
q 
Эта конфигурация является заключительной, так как машина оказалась в
состоянии остановки q 0 .
      Таким образом, слово ba переработано в слово ab .
      Полученную последовательность конфигураций можно записать более
коротким способом. Конфигурация (1) записывается в виде следующего слова
в алфавите A � Q : q1ba (содержимое обозреваемой ячейки записано справа от
состояния, в котором находится данный момент машина). Далее, конфигура-
ция (2) записывается так: q3a , конфигурация (3) – aq3 � , и наконец, (4) – abq0 .
Вся последовательность записывается так: q1ba � �q3 a � aq3 � � abq0 .
      Пример 2. Применить машину Тьюринга T1 из примера 1 к слову
bbabb, исходя из начального положения, при котором в состоянии q1 обо-
зревается крайняя левая ячейка, в котором содержится символ этого слова.


                                       Решение


    (1)                 b       b        a        b       b

                       q1

    (2)                �        b        a        b       b

                                q3

    (3)                �        b        a        b       b

                                         q3

    (4)                �        b        a        b       b

                                                 q3

    (5)                �        b        a        b       b

                                                          q3


                                       13

Страницы