Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции ленты, считающейся условно бесконечной в обе стороны. В каждой клетке может быть записан символ из фиксированного алфавита. В любой конкретный момент головка обозревает одну клетку и способна работать только с ней.
Работа машины Поста определяется программой с конечным числом строк. Программы состоит из команд, имеющих по 3 поля, в которых записываются: № команды, операция и отсылка.
Для машины Поста определены операции 6 видов:
1. Движение головки на 1 клетку вправо.
2. Движение головки на 1 клетку влево.
3. Запись метки.
4. Удаление метки.
5. Условный переход по метке.
6. STOP - остановка (завершение работы машины Поста);
Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). После запуска возможны варианты:
· работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
· работа может закончиться командой Stop;
· работа никогда не закончится
.