Машина Поста

Машина Поста

Среда - бесконечная информационная лента, разделенная на позиции (клетки). Одна из клеток выделена меткой (дважды щелкнув в клетку - галочка). 

Ленту можно двигать с помощью стрелочек слева и справа. 

Вдоль ленты движется каретка  (смотри координату 0) в виде выделенного квадрата. Она может передвигаться шагами; один шаг - смещение на одну клетку вправо или влево. 

Клетка, которая выделена кареткой, называется текущей.

Назначение исполнителя: преобразование записи на информационной ленте.

Данные: определенная расстановка меток в позициях информационной ленты.

Действия исполнителя: с помощью каретки машина Поста может:

• распознать, клетка пустая или помеченная;
• стереть метку в текущей клетке;
• поставить метку в пустую текущую клетку

Система команд исполнителя:
n.→m      Сдвиг каретки на одну позицию вправо и переход к команде номер m.

n.←m      Сдвиг каретки на одну позицию влево и переход к команде номер m.
n. ⋁ m      В текущую пустую клетку поставить метку и перейти к команде m.
n.⇳ m       Стереть метку в текущей клетке и перейти к команде m.
n. ? m,k     Проверка состояния клетки; если клетка пустая, то перейти к команде m, иначе перейти к команде k.
n.!             Стоп машина

Программа "Эмулятор Поста Тьюринга".
Информация основана на материалах учебника Семакина И. Хеннера Е.

Самостоятельная работа по теме «Машина Поста»

     1.  На информационной ленте машины Поста на расстоянии в N клеток друг от друга расположены две помеченные метками клетки. Начальное положение каретки – под левой из помеченных клеток. Какую работу выполнит машина Поста по программе?

    1.→2

    2.? 1,3

    3.← 4

    4. ? 3,1

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

 (каретка стоит на крайней левой метке):

Н.с.

●

●

●

●

●

●

●

●

●

●

●

●

●

К.с.

3.       Написать для машины Поста программу сложения двух чисел, записанных на ленте и

 расположенных через одну пустую клетку друг от друга. Начальное положение каретки под пустой клеткой, отделяющей числа.

4.       Написать для машины Поста программу вычитания двух чисел, записанных на ленте и расположенных через одну пустую клетку друг от друга. Уменьшаемое – не меньше вычитаемого. Начальное положение каретки под пустой клеткой, отделяющей числа.

 Указание: стирать метки – по одной у каждого числа, пока у вычитаемого не кончатся все метки

5.  Используя программу вычитания, проверить:

1)       Что получится, если уменьшаемое равно вычитаемому?

2)       Что получится, если уменьшаемое меньше вычитаемого?