Машина Поста
Машина Поста
Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Машина Поста состоит из …
- бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),
- головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.
Текущее состояние машины Поста описывается состоянием ленты и положением каретки.Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.
Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:
i K j,
где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
- V j - поставить метку, перейти к j-й строке программы.
- X j - стереть метку, перейти к j-й строке программы.
- <- j - сдвинуться влево, перейти к j-й строке программы.
- -> j - сдвинуться вправо, перейти к j-й строке программы.
- ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.
- ! – конец программы (стоп).
У команды «стоп» отсылки нет.