Задача 3. Изобразите на ленте в алфавите {s0, |} набор чисел 1, 2, 3 и имитируйте работу машины C (изобразите ленту после каждого такта машины до ее остановки).

Изобразите на ленте в алфавите {s₀, |} набор чисел 1, 2, 3 и имитируйте работу машины C (изобразите ленту после каждого такта машины до ее остановки).

Пример 4.

Машина D, отправляясь от воспринятого в стандартном положении числа, не самого правого на ленте, заполняет промежуток из пустых клеток (если имеется такой) между этим числом и ближайшим справа, оставляя между ними пустую клетку, и останавливается, воспринимая в стандартном положении получающееся число.

Так, машина D, примененная к ленте

s0

|

|

s0

s0

s0

|

s0

|

|

s0

s0

s0

q1

в качестве результата выдает следующую запись на ленте:

s0

|

|

|

|

s0

|

s0

|

|

s0

s0

s0

q0

Так работает машина с программой, данной в таблице 8.

Таблица 8

D	s0	|
q1		|Пq2
q2	|Пq2	|Лq3
q3		s0Лq0

Задача 4.

Изобразите на ленте числа 3 и 2 в алфавите {s₀, |}, отделенные друг от друга четырьмя пустыми ячейками. Имитируйте работу машины D применительно к этой записи на ленте.

Пример 5.

Машина r, примененная к произвольной записи на ленте, сдвигает воспринимаемую ячейку на одну ячейку вправо и затем останавливается, не изменяя записи на ленте.

Так работает машина с программой, данной в таблице 9.

Таблица 9

r	s0	|
q1	s0Пq0	|Пq0

Пример 6.

Машина l, примененная к произвольной записи на ленте, сдвигает воспринимаемую ячейку на одну ячейку влево и затем останавливается, не изменяя записи на ленте.