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

q0 

_1.5 

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

_1.0 

_40   1   2   3   4   5   6   7 

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

¦   ¦   ¦ ^ ¦ $ ¦ $ ¦ $ ¦ $ ¦ ^ ¦    ¦ 

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

q0 

_1.5 

___2Пример_2. 

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

___2Решение. 

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

'*'. 

_1.0 

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

| q0 => ^ Вправо   q2       +--------------------------+ 

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

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

^ q0 => ^ Вправо   q0       ¦  |  ¦ ^Пq2 ¦ |Лq1 ¦ |Пq2 ¦ 

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

^ q2 => | На_месте q1       ¦  ^  ¦ ^Пq0 ¦ ^Пq0 ¦ |Нq1 ¦ 

* q0 => ^ Стоп     q0       +-----¦------+------+------¦ 

* q1 => * Влево    q1       ¦  *  ¦ ^Сq0 ¦ *Лq1 ¦ *Пq2 ¦ 

* q2 => * Вправо   q2       +--------------------------+ 

_1.5 

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

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

. 

- 19 - 

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

_1.0 

_40   1   2   3   4   5   6   7 

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

¦   ¦ ^ ¦ | ¦ | ¦ * ¦ | ¦ | ¦ ^ ¦ 

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

q0 

_1.5 

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

_1.0 

_40   1   2   3   4   5   6   7   8   9 

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

¦   ¦ ^ ¦ ^ ¦ ^ ¦ ^ ¦ | ¦ | ¦ | ¦ | ¦ ^ ¦ 

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

q0 

_1.5 

___2Пример_3. 

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

___2Решение. 

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

жаются в виде палочек '|' и разделены '*'. 

_1.0 

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

| q0 => ^ Вправо   q2    +---------------------------------+ 

| q1 => | Влево    q1    ¦     ¦  q0  ¦  q1  ¦  q2  ¦  q3  ¦ 

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

| q3 => ^ Влево    q1    ¦  |  ¦ ^Пq0 ¦ |Лq1 ¦ |Пq2 ¦ ^Лq1 ¦ 

^ q0 => ^ Вправо   q0    +-----¦------+------+------+------¦ 

^ q1 => ^ Вправо   q0    ¦  ^  ¦ ^Пq0 ¦ ^Пq0 ¦ ^Нq3 ¦ ^Лq3 ¦ 

^ q2 => ^ На_месте q3    +-----¦------+------+------+------¦ 

^ q3 => ^ Влево    q3    ¦  *  ¦ ^Сq0 ¦ *Лq1 ¦ *Пq2 ¦ *Нq0 ¦ 

* q0 => ^ Стоп     q0    +---------------------------------+ 

* q1 => * Влево    q1 

* q2 => * Вправо   q2 

* q3 => * На_месте q0 

_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 

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

¦ ^ ¦ ^ ¦ ^ ¦ ^ ¦ | ¦ ^ ¦ ^ ¦ ^ ¦   ¦ 

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

q0 

_1.5 

. 

- 20 - 

___2Пример_4. 

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

n+1 (n>1). 

___2Решение. 

_1.1 

0 q0 => ^ Стоп  q0       6 q0 => ^ Стоп  q0 

1 q0 => ^ Стоп  q0       7 q0 => ^ Стоп  q0 

2 q0 => ^ Стоп  q0       8 q0 => ^ Стоп  q0 

3 q0 => ^ Стоп  q0       9 q0 => 0 Влево q0 

4 q0 => ^ Стоп  q0       ^ q0 => 1 Стоп  q0