Машина Поста - абстрактная вычислительная машина, предложенная в 1936 г.

американским математиком и логиком Эмилем Леоном Постом (родился 11 февраля 1897 года в польском городе Августов, умер 21 апреля 1954 г. в Нью-Йорке) предназначена для выполнения арифметических действий с целыми неотрицательными числами. Машина имеет вид ленты, бесконечно простирающейся в обе стороны и разделенной на секции. В каждой секции может быть либо не записано ничего (пустая секция), либо записана метка в виде латинской буквы v (отмеченная секция). Вдоль ленты перемещается курсор в виде черного квадрата, который печатает и стирает метки на ленте. Числа кодируются следующим образом: ноль - одна отмеченная секция, единица - массив из двух идущих подряд отмеченных секций, двойка - массив из трех идущих подряд отмеченных секций и т. д. Машина действует по специально составленной программе, состоящей из команд шести видов (движения курсора на одну секцию вправо и влево, печатание и стирание метки в секции, обозреваемой курсором в текущий момент времени, выбор в зависимости от того, пуста или отмечена обозреваемая секция, остановка).
При этом исключительную роль играет взаимное положение курсора и записи чисел, с которыми необходимо произвести вычисления, в начальном состоянии машины, т. е. способ хранения данных. Например, для выполнения простейшей арифметической операции - прибавлении единицы к данному целому неотрицательному числу - в простейшем случае (в начальном состоянии курсор обозревает самую левую или самую правую секцию записи исходного числа) требуется простая программа из трех команд - движение влево (соответственно вправо), запись метки и остановка, а в самом сложном случае (взаимное положение курсора и записи числа заранее неизвестно) программа очень сложна и состоит из двадцати семи команд (ее можно сократить до дадцати трех команд, но время выполнения программы при этом в ряде случаев возрастает). О машине Поста и задаче прибавления единицы рассказывается на странице "Машина Поста".
Кроме того, в машине Поста возможны те же три исхода выполнения программы, что и в современных ЭВМ - результативная остановка (машина остановилась по команде stop), аварийная остановка (машина выполнила некорректную операцию), бесконечная работа машины (программа зациклилась).