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

_1.1 

_21) ^ q1  => ^ Вправо   q2   _2 2) 2 q1  => 2 Вправо   q1 

^ q2  => @ Вправо   q3   _2   ^ q1  => 1 Вправо   q2 

@ q3  => ^ Вправо   q1   _2   ^ q2  => 2 На_месте q1 

_23) ^ q1  => # Вправо   q2   _2 4) ? q1  => ? Вправо   q1 

# q2  => ^ На_месте q3   _2   ^ q1  => * Вправо   q2 

^ q3  => # Вправо   q4   _2   ^ q2  => ^ Вправо   q3 

# q4  => ^ Влево    q1       ^ q3  => ? На_месте q1 

_25) ^ q0  =>  ^ Стоп    q0   _2 6) $ q1  => * Вправо   q2 

@ q0  =>  $ Вправо  q1   _2   ^ q1  => $ На_месте q1 

$ q1  =>  @ Вправо  q0   _2   ^ q2  => ^ Вправо   q1 

_27) 3 q1  => 3 Вправо   q2    _28) 8 q1  => 8 Вправо   q3 

4 q1  => 4 Вправо   q3    _2  8 q2  => 8 Вправо   q1 

^ q1  => 3 На_месте q1       ^ q1  => ^ Вправо   q2 

^ q2  => 4 На_месте q1       ^ q2  => 8 На_месте q1 

^ q3  => ^ Вправо   q1       ^ q3  => 8 На_месте q2 

_29) ^ q1  => ^ Влево    q2    _210) В q1  => ^ Вправо   q1 

^ q2  => * На_месте q3        ^ q1  => В На_месте q1 

* q3  => ^ Вправо   q4 

^ q4  => ^ Вправо   q1 

_1.5 

___2Задание II_.. 

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

. 

- 23 - 

_1.0 

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

¦     ¦  q0  ¦  q1  ¦  q2  ¦  q3  ¦ 

+-----+------+------+------+------¦ 

¦  |  ¦ ^Пq1 ¦ |Пq1 ¦ ^Лq3 ¦ |Лq3 ¦ 

+-----¦------+------+------+------¦ 

¦  ^  ¦      ¦ ^Лq2 ¦      ¦ ^Пq0 ¦ 

+-----¦------+------+------+------¦ 

¦  *  ¦ *Сq0 ¦ *Пq1 ¦      ¦ *Лq3 ¦ 

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

_1.5  а лента будет имеет такой вид: 

_1.0 

n                     m            (n<m) 

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

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

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

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

q0 

_1.5 

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

_1.0 

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

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

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

q0 

_1.5 

Программа для машины Тьюринга задана командами: 

_1.1 

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

| q1  => | Влево   q1        * q0  => ^ Стоп    q0 

| q2  => | Вправо  q2        * q1  => * Влево   q1 

^ q1  => | Вправо  q2        * q2  => * Вправо  q2 

_1.5 

Что будет написано на ленте после работы машины по данному ал-  горитму? 

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

_1.0 

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

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

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

q0 

_1.5 

Машина работает в соответствии со следующей программой: 

_1.1 

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

| q1  => | Влево   q1      ^ q3  => ^ Влево   q0 

| q2  => ^ Вправо  q3      * q0  => ^ Стоп    q0 

| q3  => | Вправо  q3      * q1  => * Влево   q2 

^ q0  => ^ Вправо  q0      * q3  => * Вправо  q3 

^ q1  => ^ Вправо  q2 

_1.5 

Какую операцию выполняет машина? 

_24. На ленте машины Тьюринга написано два двоичных числа,  раз-  деленных звездочкой. 

_1.0 

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

¦ ^ ¦ 1 ¦ 0 ¦ 1 ¦ 1 ¦ * ¦ 1 ¦ 0 ¦ 1 ¦ ^ ¦   ¦ 

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

q0 

_1.5 

Работа машины определяется следующей программой: 

_1.1 

1 q0 => 0 Влево  q1      0 q4 => 0 Вправо q4 

1 q1 => 1 Влево  q1      0 q5 => 0 Влево  q5 

1 q2 => 0 Влево  q3      * q1 => * Влево  q2 

1 q3 => 1 Влево  q3      * q4 => * Вправо q4