Машина Поста — это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. 34

Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы. 3

Структура машины Поста:

• Лента бесконечна и разделена на секции одинакового размера — ячейки. 3 В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка. 3
• Каретка (называемая также считывающей и записывающей головкой) может передвигаться вдоль ленты влево и вправо. 3 Когда она неподвижна, она стоит против ровно одной ячейки ленты. 3

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