Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:i K j,где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
V j - поставить метку, перейти к j-й строке программы. X j - стереть метку, перейти к j-й строке программы. <- j - сдвинуться влево, перейти к j-й строке программы. -> j - сдвинуться вправо, перейти к j-й строке программы. ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы. ! – конец программы (стоп).У команды «стоп» отсылки нет. После запуска возможны варианты:
- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой Stop;
- работа никогда не закончится.
Алгоритм "разность двух чисел"
1. ←
2. ? 1, 3
3. ←
4. ? 5, 3
5. 0
6. →
7. ? 8, 6
8. 0
9. →
10. ? 1, 11
11. STOP
Комментариев нет:
Отправить комментарий