среда, 18 декабря 2013 г.

Машина Поста

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 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

Комментариев нет:

Отправить комментарий