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

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

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

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

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

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

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

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

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

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

Пример работы машины Поста:
1. → 2
2. ? 1;3
3. ←4
4. V 5
5. !

Пример работы машины Поста:
Задача 2: стереть метку в текущей клетке и присоединить ее слева к группе меток, расположенных справа от каретки
Решение:

Задача 3
. – поставить метку

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

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

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