Машина Поста

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Маши́на По́ста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (англ. 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.

См. также[править | править вики-текст]

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

Литература[править | править вики-текст]

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