Программирование машины Тьюринга, страница 11

5 q0 => ^ Стоп  q0 

_1.5 

Начальное состояние машины Тьюринга: обозреваем последнюю циф-  ру в состоянии q0. 

Каретка указывает на ячейку: 3 

Состояние ленты перед выполнением программы, с помощью которой  мы хотим увеличить на 1 число 349: 

_1.0 

_40   1   2   3   4   5   6   7 

--------------------------------- 

¦ ^ ¦ 3 ¦ 4 ¦ 9 ¦ ^ ¦ ^ ¦   ¦   ¦ 

--------------------------------- 

q0 

_1.5 

Состояние ленты после выполнения программы: 

_1.0 

_40   1   2   3   4   5   6   7 

------------------------------------- 

¦ ^ ¦ 3 ¦ 5 ¦ 0 ¦ ^ ¦ ^ ¦   ¦   ¦   ¦ 

------------------------------------- 

q0 

_1.5 

___2Пример_5. 

Составить программу для машины Тьюринга,  реализующую алгоритм  проверки правильности расстановки круглых скобок для слова, запи-  санного на ленте машины Тьюринга. 

___2Решение. 

На ленту машины Тьюринга  подается  строка  символов,  которая  состоит из символов:  #, (, ). Если в строке будет правильное ко-  личество скобок,  то в результате на ленте появится  число  1.  В  противном случае - 0. 

_1.1 

( q0 => ( Вправо   q0         ) q0 => * Влево    q1 

* q0 => * Вправо   q0         # q0 => # Влево    q2 

( q1 => * Вправо   q0         * q1 => * Влево    q1 

# q1 => 0 Вправо   q4         ( q2 => # Влево    q3 

* q2 => # Влево    q2         # q2 => 1 На_месте q2 

( q3 => # Влево    q3         * q3 => # Влево    q3 

- 21 - 

# q3 => 0 На_месте q3         ( q4 => # Вправо   q4 

) q4 => # Вправо   q4         * q4 => # Вправо   q4 

_1.5 

Начальное состояние машины Тьюринга: ( q0 

Каретка указывает на ячейку: 1 

Состояние ленты перед выполнением программы: 

_1.0 

_40   1   2   3   4   5   6   7 

--------------------------------- 

¦ # ¦ ( ¦ ( ¦ ) ¦ ( ¦ ) ¦ # ¦   ¦ 

--------------------------------- 

q0 

_1.5 

Состояние ленты после выполнения программы: 

_1.0 

_40   1   2   3   4   5   6   7 

--------------------------------- 

¦ # ¦ 0 ¦ # ¦ # ¦ # ¦ # ¦   ¦   ¦ 

--------------------------------- 

q0 

_1.5 

___2Пример_6. 

Составить программу и функциональную схему для машины  Тьюрин-  га, реализующей алгоритм проверки состоит ли данное слово из двух  одинаковых символов или двух разных. 

___2Решение. 

На ленту машины Тьюринга подается пара символов.  В результате  ее работы на ленте должен появиться символ '*', если символы дан-  ного слова одинаковы.  В противном случае состояние ленты  должно  остаться без изменения. 

_1.0 

_3Программа                Функциональная схема 

0 q0 => 0 Вправо q1       +--------------------------+ 

0 q1 => 0 Влево  q2       ¦     ¦  q0  ¦  q1  ¦  q2  ¦ 

0 q2 => * Стоп   q2       +-----+------+------+------¦ 

1 q0 => 1 Вправо q0       ¦  0  ¦ 0Пq1 ¦ 0Лq2 ¦ *Сq2 ¦ 

1 q1 => 1 Вправо q2       +-----¦------+------+------¦ 

1 q2 => * Стоп   q2       ¦  1  ¦ 1Пq1 ¦ 1Пq2 ¦ *Сq2 ¦ 

+--------------------------+ 

_1.5 

Начальное состояние машины Тьюринга: 0 q0 

Каретка указывает на ячейку: 1 

Состояние ленты перед выполнением программы: 

_1.0 

_40   1   2   3   4 

--------------------- 

¦ ^ ¦ 0 ¦ 0 ¦ ^ ¦ ^ ¦ 

--------------------- 

q0 

_1.5 

. 

- 22 - 

Состояние ленты после выполнения программы: 

_1.0 

_40   1   2   3   4 

--------------------- 

¦ ^ ¦ 0 ¦ 0 ¦ * ¦ ^ ¦ 

--------------------- 

q2 

_1.5 

_2УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 

___2Задание I_.. 

Объясните работу машины Тьюринга по приведенной ниже  програм-  ме. Составьте функциональную схему и укажите состояние ленты пос-  ле ее выполнения.  Машина начинает с "пустого" начального состоя-  ния (т.е. такого, при котором все секции заполнены символом внеш-  него алфавита,  обозначающего пустой знак '^'). Начальное внешнее  и внутреннее состояния машины Тьюринга: ^ и q1.