Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:
где i — номер команды, K – действие каретки, j — номер следующей команды (отсылка).
Что такое машина Поста. Душкин объяснит
Всего для машины Поста существует шесть типов команд:
V j – поставить метку, перейти к j-й строке программы.
X j – стереть метку, перейти к j-й строке программы.
-> j – сдвинуться вправо, перейти к j-й строке программы.
? j1; j2 – если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.
! – конец программы (стоп).
У команды «стоп» отсылки нет. После запуска возможны варианты:
- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой Stop;
- работа никогда не закончится.
Пример: вычитание натуральных чисел p — q
Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»
Сложение двух чисел тривиально — достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:
1. 0 — стираем левый символ у Q
4. Stop — стоп если затерли Q=0
6. ? 5, 7 — цикл поиска P
7. 0 — стираем правый символ у P
Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами)
Источник: studfile.net
Уроки 15 — 16
Автоматическая обработка информации
Практическая работа № 2.2 «Автоматическая обработка данных»
Цель работы: знакомство с основами теории алгоритмов на примере решения задач на программное управление алгоритмической машиной Поста.
Используемое программное обеспечение: имитатор машины Поста, (который можно скачать отсюда).
Информатика. Машина Поста.
Система команд машины Поста: (везде буква n обозначает номер текущей команды):
Задание 1
Составить программу перевода информационной ленты машины Поста из начального состояния (н.с.) в конечное (к.е.):
Задание 2
1. Выполнить на машине Поста программу:
2. Какую задачу решает исполнитель по этой программе?
3. Что произойдет, если начальное состояние информационной ленты будет иметь следующий вид?
В следующих задачах считается, что n расположенных подряд меток обозначают число n (непозиционная система счисления с основанием 1).
Задание 3
Написать для машины Поста программу сложения двух чисел, записанных на ленте и расположенных через одну пустую клетку друг от друга. Начальное положение каретки — под пустой клеткой, отделяющей числа.
Задание 4
Написать для машины Поста программу вычитания двух чисел, разделенных одной пустой клеткой. Уменьшаемое не меньше вычитаемого. Начальное положение каретки — под пустой клеткой, отделяющей уменьшаемое от вычитаемого.
Указание. Стирать метки по одной у каждого числа, пока у вычитаемого не кончатся все метки.
Задание 5
Используя программу вычитания, проверить, что получится, если:
а) уменьшаемое равно вычитаемому;
б) уменьшаемое меньше вычитаемого.
Задание 6
Написать для машины Поста программу деления числа, записанного метками, на 2. Исходное число должно делиться на 2 без остатка.
Указание. Стереть каждую вторую метку; уплотнить оставшиеся метки.
Задание 7
Используя программу деления числа на 2: а) проверить, что получится для числа 2; б) модифицировать программу с учетом числа 2.
Указание. Справа от пустой клетки поставить метку, а слева стереть две метки. Так поступать до тех пор, пока слева остаются метки.
Задание 8
На информационной ленте машины Поста на расстоянии в га клеток друг от друга расположены две помеченные метками клетки. Начальное положение каретки — под левой из помеченных клеток. Какую работу выполнит Машина Поста по программе?
Задание 9
Написать для машины Поста программу умножения на 2 числа, записанного метками на ленте.
Указание. Через одну пустую клетку поставить две метки, а в исходном числе стереть одну. Так поступать, пока в исходном числе остаются метки.
Задание 10*
Написать для машины Поста программу, проверяющую, делится ли записанное метками число на 5.
Задание 11*
На информационной ленте машины Поста помечена 2n — 1 клетка. Составить программу отыскания средней помеченной клетки и стирания метки в ней.
Задание 12*
На информационной ленте машины Поста расположены два массива помеченных клеток. Написать программу стирания меток, расположенных в большем массиве.
Следующая страница Автоматическая обработка информации
Источник: xn—-7sbbfb7a7aej.xn--p1ai