Устройство и система команд алгоритмической машины Поста

1. Устройство и система команд алгоритмической машины Поста.

2. Машина Поста – это абстрактная вычислительная машина, созданная для уточнения понятия алгоритма. Представляет собой

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

3. История создания

В 1936 г. американский
математик Эмиль Пост в
статье описал систему,
обладающую
алгоритмической простотой
и способную определять,
является ли та или иная
задача алгоритмически
разрешимой.

4. Устройство машины

Бесконечная
лента
Машина
Поста
Каретка

5. Принцип действия

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

6.

Каждая команда имеет следующий
синтаксис:
i K j,
где i - номер команды,
K – действие каретки,
j - номер следующей команды
(отсылка).

7.

Всего для машины Поста существует шесть
типов команд:
V j - поставить метку, перейти к j-й строке
программы.
↕ j - стереть метку, перейти к j-й строке
программы.
← j - сдвинуться влево, перейти к j-й строке
программы.
→ j - сдвинуться вправо, перейти к j-й строке
программы.
? j1; j2 - если в ячейке нет метки, то перейти к j1-й
строке программы, иначе перейти к j2-й строке
программы.
! – конец программы (стоп).

8. Варианты окончания выполнения программы:

Команда «стоп»;
Выполнение недопустимой команды;
Уход в бесконечность, зацикливание.

9.

Программой машины Поста будем
называть конечный список команд машины
Поста, обладающий следующими двумя
свойствами:
• На первом месте в этом списке стоит команда
с номером 1, на втором месте - команда с
номером 2 и т.д.;
• Отсылка любой из команд списка совпадает с
номером некоторой команды списка.

10. Пример работы машины Поста:

Задача 1: увеличить число 3 на единицу.
(изменить значение в памяти с 3 на 4).
Решение:
Целое положительное число на ленте машины Поста представимо
идущими подряд метками, которых на одну больше, чем
кодируемое число. Это связано с тем, что одна метка обозначает
ноль, а уже две – единицу, и т.д.
Предположим, что точно известно, что каретка стоит где-то слева от
меток и направлена на пустую ячейку.

11. Пример работы машины Поста:

1. → 2
2. ? 1;3
3. ←4
4. V 5
5. !

12. Пример работы машины Поста:

Задача 2: стереть метку в текущей клетке и
присоединить ее слева к группе меток,
расположенных справа от каретки
стирание метки, переход к следующей команде
Решение: 1. ↕2
2. → 3
смещение каретки на шаг вправо
3. ? 2;4
если клетка пустая, то перейти к команде 2,
иначе – к команде 4
4. ←5
сдвиг каретки влево
5. V 5
Запись метки в пустую клетку
6. !
Стоп, остановка машины

13. Задача 3

.–
поставить метку

14. Задача 4

Решение:
1. ←2
2. V 3
3. ←4
4. ↕5
5. ←6
6. V 7
7. ←8
8. ←9
9. !

15. Вывод

Автоматическая обработка информации возможна,
если:
Информация представлена в формализованном виде
– в конечном алфавите некоторой знаковой системы;
Реализован исполнитель, обладающий конечной
системой команд;
Реализовано программное управление работой
исполнителя.
Машина Поста – пример автоматического исполнителя
обработки информации с ограниченными
возможностями.

16. Домашнее задание

Учебник
Выучить п 10
Задачник
Выполнить письменно стр 186 №1, стр 187 №5

17. Дополнительные источники информации:

Википедия:
https://ru.wikipedia
Интернет-ресурс «Планета информатики» :
http://www.inf1.info/machinepost.