Работа машины
Машина Поста, несмотря на внешнюю
простоту, может производить
различные вычисления, для чего надо
задать начальное состояние каретки и
программу, которая эти вычисления
сделает. Машиной эта математическая
конструкция названа потому, что при ее
построении используются некоторые
понятия реальных машин (ячейка
памяти, команда и др.). Условимся
каждый шаг программы обозначать
номером. Команды машины будем
обозначать следующим образом: