Машина Поста

Для уточнения понятия алгоритма амер. математиком Постом (1937 г.) было предложено строгое математическое построение, которое было названо «машиной», т. к. в нем используются некоторые понятия реальных машин – память, команда и др.

– бесконечная лента, в ячейках которой можно записывать всего два знака: 1 (ставить метку) или 0 (стирать метку) и головка для чтения/записи, управляемая программой.
Машина Поста (МП)

Система команд МП

Недопустимые действия МП
Попытка записать 1 (отметку) в заполненную ячейку
Попытка стереть отметку в пустой ячейке
Уход головки в бесконечность или зацикливание

состоит из пронумерованных строк, в каждой строке записывается только одна команда.
Программа МП

На ленте проставлена отметка в одной единственной ячейке.
Головка стоит слева на некотором расстоянии. Надо стереть отметку и остановить головку слева от ячейки.
Пример
→ 2
? 1 ; 3
X 4
← 5
!
Программа МП задачи

– всякий алгоритм представим в форме машины Поста.
Тезис Поста

– программа для машины Поста, приводящая к решению поставленной задачи.
Алгоритм (по Посту)
Если для решения задачи можно построить машину Поста, то она алгоритмически разрешима.