Машина Поста

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

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

Система команд МП Обозначения V i Записать 1 (отметку), перейти к i - той строке программы X i Записать 0 (стереть отметку), перейти к i -той строке i Шаг вправо, перейти к i -той строке i Шаг влево, перейти к i -той строке ? i ; j Если в ячейке 0, то перейти к i -той строке, иначе перейти к j -той строке ! Останов

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

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

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

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

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

В теории алгоритмов доказано, что машина Поста и машина Тьюринга эквивалентны по своим возможностям несмотря на то, что МП проще, чем МТ.