Машина Поста в теории алгоритмов работает следующим образом: 13

1. Машина состоит из каретки (считывающей и записывающей головки) и бесконечной в обе стороны ленты, разбитой на ячейки. 13 Каждая ячейка ленты может быть либо пустой (0), либо помеченной меткой (1). 1
2. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. 1
3. Алгоритм работы машины задаётся как программа для универсального исполнителя. 1 Программа состоит из конечного числа строк и использует всего 6 команд: 1

• N. → J — сдвиг вправо; 1
• N. ← J — сдвиг влево; 1
• N. 1 J — запись метки; 1
• N. 0 J — удаление метки; 1
• N. ? J1, J0 — если в ячейке есть метка, то перейти к j1 строке программы, иначе перейти к j0 строке программы; 1
• N. Stop — остановка. 1

1. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). 13

Попытка стереть метку там, где её нет, или поставить метку повторно считается ошибкой, и машина аварийно останавливается. 1