Машина Поста

Материал из Циклопедии
Перейти к: навигация, поиск
Автоматическая обработка данных. Машина Поста // Видеоуроки по информатике [14:54]

Машина Поста (МП) — это абстрактная вычислительная машина для выполнения программ, предложенная американским математиком Эмилем Леоном Постом в 1936 году.

Содержание

[править] Состав МП

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

[править] Виды команд:

  • сдвиг вправо
  • сдвиг влево
  • запись 1
  • запись 0
  • переход (безусловный)
  • условный переход
  • стоп

Введём обозначения:

n — номер командной строки в программе;

n1 — номер командной строки, которой передаётся управление;

n2 — номер альтернативной командной строки, которой передаётся управление;

R — сдвиг вправо;

L — сдвиг влево;

1 — запись 1;

0 — запись 0;

? — проверка условия;

S — стоп.

[править] Виды командных строк:

nR — сдвиг на 1 ячейку вправо и переход к следующей строке;

nRn1 — сдвиг на 1 ячейку вправо и переход к строке n1;

nL — сдвиг на 1 ячейку влево и переход к следующей строке;

nLn1 — сдвиг на 1 ячейку влево и переход к строке n1;

n1 — запись 1 и переход к следующей строке;

n1n1 — запись 1 и переход к строке n1;

n0 — запись 0 (стирание 1, если она была) и переход к следующей строке;

n0n1 — запись 0 и переход к строке n1;

n?n1,n2 — если в ячейке 1, то переход к строке n1, иначе — переход к строке n2;

n?n1 — если в ячейке 1, то переход к строке n1, иначе — переход к следующей строке;

n?,n2 — если в ячейке 1, то переход к следующей строке, иначе — переход к строке n2;

nS — остановка работы.

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

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

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

[править] Пример задачи

МП11.JPG, где x, y - неотрицательные целые числа.

[править] Программа для МП

МП12.JPG

[править] Таблица для программы

МП13.JPG

[править] Примеры работы МП:

Введём обозначения:

1 — число 0;

11 — число 1;

111 — число 2;

1x+1 — неотрицательное целое число x;

1y+1 — неотрицательное целое число y;

1x+101y+1 — набор значений аргументов (x,y).

[править] Пример 1

Входные данные: 11011.

МП14.JPG

Выходные данные: 014011.

[править] Пример 2

Входные данные: 111101.

МП15.JPG

Выходные данные: 11101400.

[править] Пример 3

Входные данные: 1110111.

МП16.JPG

Выходные данные: 111101400.

[править] Другие алгоритмы

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты