Требования к отчету
Отчет должен содержать:
название работы, постановку задачи и сведения о последовательности её выполнения;
скриншот работающей программы (результаты работы);
ответы на контрольные вопросы из Приложения Б, указанные преподавателем.
Решение задач на эмуляторе машины Поста
Цель занятия - изучение основ работы машины Поста на компьютерном эмуляторе, решение задач по реализации арифметических действий.
Объем занятия – 2 часа.
Общие сведения
Машина Поста
(МП) - абстрактная вычислительная машина,
предложенная Эмилем
Леоном Постом(Emil
L. Post), которая
отличается отмашины
Тьюрингабольшей простотой. Согласно
тезису Поста, любой алгоритм может быть
записан в виде программы для машины
Поста. Доказано, что машина Поста по
своим возможностям эквивалентнамашине
Тьюрингаинормальным
«алгорифмам» Маркова; обе машины
были созданы для уточнения понятия
«алгоритм».
Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой – 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:
i K j,
где i – номер команды, K – действие каретки, j – номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
V j – поставить метку, перейти к j-й строке программы.
X j – стереть метку, перейти к j-й строке программы.
<– j – сдвинуться влево, перейти к j-й строке программы.
–> j – сдвинуться вправо, перейти к j-й строке программы.
? j1; j2 – если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.
! – конец программы (стоп).
У команды «стоп» отсылки нет. После запуска возможны варианты:
работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
работа может закончиться командой Stop;
работа никогда не закончится.
Пример: вычитание натуральных чисел p – q
Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
P |
|
|
|
|
Q |
|
|
|
|
Сложение двух чисел тривиально – достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:
1. 0 – стираем левый символ у Q
2. →
3. ? 4, 5
4. Stop – стоп если затерли Q = 0
5. ←
6. ? 5, 7 – цикл поиска P
7. 0 – стираем правый символ у P
8. →
9. ? 8, 1 – ищем Q
Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами).