Машина Поста - математическое построение, предназначенное для уточнения понятия алгоритма. Машина Поста состоит:
- из неограниченной в обе стороны ленты, разделенной на ячейки;
- из головка чтения/записи, которая может перемещаться вдоль ленты и управляется программой на специальном языке из шести команд.
Доказано, что классы алгоритмов, представленных в форме машины Поста, и класс алгоритмов, представленных в форме машины Тьюринга, совпадают.