Машина Поста

Маши́на По́ста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (англ. Emil Leon Post), которая отличается от машины Тьюринга большей простотой. Обе машины алгоритмически «эквивалентны» и были придуманы для уточнения понятия «алгоритм». В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима также в форме последовательности команд для машины Поста.

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты (см. пример ниже). Каждая ячейка ленты может находиться в 2 состояниях — быть либо пустой — 0, либо помеченной меткой 1. За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.

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

    i K j

где i — номер команды, K — действие каретки, j — номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

   V j      - поставить метку, перейти к j-й строке программы.
   X j      - стереть метку, перейти к j-й строке программы.
   ← j      - сдвинуться влево, перейти к j-й строке программы.
   → j      - сдвинуться вправо, перейти к j-й строке программы.
   ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.
   !        – конец программы (стоп).

В команде «стоп» переход на следующую строку не указывается.

После программы запуска возможны варианты:

• работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
• работа может закончиться командой Stop;
• работа никогда не закончится.

Примеры: сложение и вычитание натуральных чисел P, Q

Пусть натуральные (целые неотрицательные) числа P и Q изображаются набором из P и Q единиц и разделены нулём. Пусть исходное положение каретки находится на крайней левой «1» группы единиц Q (помечено символом «v»).

            v
 ...00111110111000...
      ----- ---
        P    Q

Сложение двух чисел тривиально — достаточно поставить 1 между ними и стереть одно крайнее правое «1» у Q. Программа вычитания состоит из последовательного изменения крайних левых «1» у последовательности «1» в изображении Q и правых «1» у последовательности «1» в изображении P. В начале программы каретка установлена на крайнюю левую «1» у Q:

1. ←       - шаг влево
2. ? 1, 3  - если в ячейке пусто, перейти к 1 шагу, если нет, к 3
3. 0       - удалить метку
4. →       - шаг вправо
5. ? 4, 6  - если в ячейке пусто, перейти к 4 шагу, если нет, к 6
6. 0       - удалить метку
7. →       - шаг вправо
8. ? 9, 1  - если в ячейке пусто, перейти к 9 шагу, если нет, к 1
9. !       - конец

Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-й строке возможно зацикливание, если Q > P.

См. также

Другие абстрактные исполнители и формальные системы вычислений

• Нормальный алгоритм Маркова (продукционное программирование)
• Машина Тьюринга (автоматное программирование)
• Рекурсивная функция (теория вычислимости)
• Конечный автомат
• Лямбда-исчисление (функциональное программирование)
• Brainfuck (императивное программирование)

Литература

Успенский Владимир Андреевич. [math.ru/lib/files/plm/v54.djvu Машина Поста] / Гл. ред. физ.-мат. лит.. — 2-е изд., испр.. — М.: Наука, 1988. — 96 с. — (Популярные лекции по математике). — ISBN 5-02-013735-9.

Отрывок, характеризующий Машина Поста

И не успел еще Ростов разглядеть что то, вдруг зачерневшееся в тумане, как блеснул огонек, щелкнул выстрел, и пуля, как будто жалуясь на что то, зажужжала высоко в тумане и вылетела из слуха. Другое ружье не выстрелило, но блеснул огонек на полке. Ростов повернул лошадь и галопом поехал назад. Еще раздались в разных промежутках четыре выстрела, и на разные тоны запели пули где то в тумане. Ростов придержал лошадь, повеселевшую так же, как он, от выстрелов, и поехал шагом. «Ну ка еще, ну ка еще!» говорил в его душе какой то веселый голос. Но выстрелов больше не было.
Только подъезжая к Багратиону, Ростов опять пустил свою лошадь в галоп и, держа руку у козырька, подъехал к нему.
Долгоруков всё настаивал на своем мнении, что французы отступили и только для того, чтобы обмануть нас, разложили огни.
– Что же это доказывает? – говорил он в то время, как Ростов подъехал к ним. – Они могли отступить и оставить пикеты.
– Видно, еще не все ушли, князь, – сказал Багратион. – До завтрашнего утра, завтра всё узнаем.
– На горе пикет, ваше сиятельство, всё там же, где был с вечера, – доложил Ростов, нагибаясь вперед, держа руку у козырька и не в силах удержать улыбку веселья, вызванного в нем его поездкой и, главное, звуками пуль.
– Хорошо, хорошо, – сказал Багратион, – благодарю вас, г. офицер.
– Ваше сиятельство, – сказал Ростов, – позвольте вас просить.
– Что такое?
– Завтра эскадрон наш назначен в резервы; позвольте вас просить прикомандировать меня к 1 му эскадрону.
– Как фамилия?
– Граф Ростов.
– А, хорошо. Оставайся при мне ординарцем.
– Ильи Андреича сын? – сказал Долгоруков.
Но Ростов не отвечал ему.
– Так я буду надеяться, ваше сиятельство.
– Я прикажу.
«Завтра, очень может быть, пошлют с каким нибудь приказанием к государю, – подумал он. – Слава Богу».

Крики и огни в неприятельской армии происходили оттого, что в то время, как по войскам читали приказ Наполеона, сам император верхом объезжал свои бивуаки. Солдаты, увидав императора, зажигали пуки соломы и с криками: vive l'empereur! бежали за ним. Приказ Наполеона был следующий:
«Солдаты! Русская армия выходит против вас, чтобы отмстить за австрийскую, ульмскую армию. Это те же баталионы, которые вы разбили при Голлабрунне и которые вы с тех пор преследовали постоянно до этого места. Позиции, которые мы занимаем, – могущественны, и пока они будут итти, чтоб обойти меня справа, они выставят мне фланг! Солдаты! Я сам буду руководить вашими баталионами. Я буду держаться далеко от огня, если вы, с вашей обычной храбростью, внесете в ряды неприятельские беспорядок и смятение; но если победа будет хоть одну минуту сомнительна, вы увидите вашего императора, подвергающегося первым ударам неприятеля, потому что не может быть колебания в победе, особенно в тот день, в который идет речь о чести французской пехоты, которая так необходима для чести своей нации.
Под предлогом увода раненых не расстроивать ряда! Каждый да будет вполне проникнут мыслию, что надо победить этих наемников Англии, воодушевленных такою ненавистью против нашей нации. Эта победа окончит наш поход, и мы можем возвратиться на зимние квартиры, где застанут нас новые французские войска, которые формируются во Франции; и тогда мир, который я заключу, будет достоин моего народа, вас и меня.
Наполеон».


В 5 часов утра еще было совсем темно. Войска центра, резервов и правый фланг Багратиона стояли еще неподвижно; но на левом фланге колонны пехоты, кавалерии и артиллерии, долженствовавшие первые спуститься с высот, для того чтобы атаковать французский правый фланг и отбросить его, по диспозиции, в Богемские горы, уже зашевелились и начали подниматься с своих ночлегов. Дым от костров, в которые бросали всё лишнее, ел глаза. Было холодно и темно. Офицеры торопливо пили чай и завтракали, солдаты пережевывали сухари, отбивали ногами дробь, согреваясь, и стекались против огней, бросая в дрова остатки балаганов, стулья, столы, колеса, кадушки, всё лишнее, что нельзя было увезти с собою. Австрийские колонновожатые сновали между русскими войсками и служили предвестниками выступления. Как только показывался австрийский офицер около стоянки полкового командира, полк начинал шевелиться: солдаты сбегались от костров, прятали в голенища трубочки, мешочки в повозки, разбирали ружья и строились. Офицеры застегивались, надевали шпаги и ранцы и, покрикивая, обходили ряды; обозные и денщики запрягали, укладывали и увязывали повозки. Адъютанты, батальонные и полковые командиры садились верхами, крестились, отдавали последние приказания, наставления и поручения остающимся обозным, и звучал однообразный топот тысячей ног. Колонны двигались, не зная куда и не видя от окружавших людей, от дыма и от усиливающегося тумана ни той местности, из которой они выходили, ни той, в которую они вступали.