Урок №3

Урок №3. "Машина Поста"

В качестве примера автоматической обработки информации рассмотрим машину Поста.

Алгоритм по которой работает машина Поста будем называть программой.

Итак, что мы имеем у машины Поста, с чем мы будем работать:

Бесконечная информационная лента, разделенная на позиции – клетки. В каждой клетке может либо стоять, либо отсутствовать метка. Вдоль ленты движется каретка – считывающее устройство. На рисунках она обозначается стрелкой. Каретка может передвигаться право или влево. Клетку под которой установлена стрелка будем называть текущей. Каретка является еще и процессом машины. С ее помощью машина может:

1.Распознать, пустая клетка или помечена знаком;

2.Стереть знак в текущей клетке;

3.Записать знак в пустую текущую клетку.

Назначение машины Поста – производить преобразования на информационной ленте. Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное значение ленты – результат решения задачи.

Рассмотрим систему команд машины Поста. Запись любой команды начинается с ее порядкового номера в программе – n. Затем следует код операции и после него – номер следующей выполняемой команды программы – m.

Коды операций:

<- сдвиг на шаг влево.(Например: 1<-2, сдвиг каретки влево и переход на шаг 2)

->Сдвиг на шаг вправо

V запись метки в текущую пустую метку.(Например: 1 V 3, в текущей позиции ленты ставится лента и переходим к шагу 3)

↕ стирание метки в текущей клетке. (Например: 1 ↕ 2, в текущей позиции ленты стирается метка, если она есть)

! Остановка выполнения программы(Например: 3!, на шаге 3 происходит результативная остановка)

? переход в зависимости от того стоит метка или нет. (Например: 1 ? 2,3, если метка стоит, то переход на шаг 2, иначе переход на шаг 3)

Так например, чтобы получить из ленты 1 ленту 2

Необходимо выполнить следующие шаги:

1 V 2

2!

Давайте рассмотрим выполнение этот программы на эмуляторе.

Теоретический материал

По начальному состоянию машины Поста и конечному сказать, какие команды были выполнены:

1.

2.

3.

4.

5.

6.

Какой результат получится после выполнения следующей программы?

1 V 4

2 <=> 3

3 <= 2

4 => 5

5 ? 4,6;

6 !

Практическая работа

1. Назовите системой команд исполнителя машины Поста.

2. Перечислите все составляющие машины Поста.

3. Перечислите все возможные команды машины Поста.

4. В каком случае происходит безрезультатная остановка?

5. Когда количество шагов может быть больше, чем количество команд?

Контрольные вопросы