Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Машина Поста состоит из …
бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),
головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.
Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.
Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:
i K j,
где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
V j - поставить метку, перейти к j-й строке программы.
X j - стереть метку, перейти к j-й строке программы.
<- j - сдвинуться влево, перейти к j-й строке программы.
-> j - сдвинуться вправо, перейти к j-й строке программы.
? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.
! – конец программы (стоп).
У команды «стоп» отсылки нет.
Варианты окончания выполнения программы на машине Поста:
Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.
Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).
Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).
Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга.
Почему достаточно лишь два различных символа (есть метка, нет метки)? Дело в том, что любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита
Вы уже знаете о суперспособностях современного учителя?
Тратить минимум сил на подготовку и проведение уроков.
Быстро и объективно проверять знания учащихся.
Сделать изучение нового материала максимально понятным.
Избавить себя от подбора заданий и их проверки после уроков.
Просмотр содержимого документа
«Алгоритмическая машина Поста. »
Машина Поста.
Среда – бесконечная информационная лента, разделенная на позиции (клетки).
В каждой клетке может либо стоять метка (обозначается жирной точкой V ) либо – пусто. Вдоль ленты движется каретка. Она может передвигаться шагами; один шаг - смещение на одну клетку вправо или влево. Клетка, у которой установлена каретка будем называть текущей.
лента
…
…
каретка
Назначение исполнителя: преобразование записи на информационной ленте.
Данные: определенная расстановка меток в позициях информационной ленты.
Действия исполнителя: с помощью каретки машина Поста может:
распознать, клетка пустая или помеченная;
стереть метку в текущей клетке;
поставить метку в пустую текущую клетку.
Система команд исполнителя: (везде буква N обозначает номер текущей команды)
NM
Сдвиг каретки вправо, содержимое ленты не меняется. И переход к команде номер M.
NM
Сдвиг каретки влево, содержимое ленты не меняется. И переход к команде номер M.
NV M
В обозреваемую секцию ставится метка "V". Выполнение этой команды возможно только в том случае, если обозреваемыя секция пустая, в противном случае команда считается невыполнимой. И переход к команде номер M.
NM
Каретка стирает метку в обозреваемой секции. Выполнение этой команды возможно только в том случае, если обозреваемыя секция содержит метку, в противном случае команда считается невыполнимой. И переход к команде номер M.
N? M, K
Команда передачи. Проверяется содержимое текущей секции, если метки нет, то происходит передача управления команде с номером M, иначе, если метка есть - команде с номером K. Содержимое ленты не меняется.
N!
Команда останова машины. Содержимое ленты не меняется. У команды остановки отсылка не обязательна.
Пример:
V
V
V
V
V
Задание:
Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки.
2
3
? 2, 4
5
V 6
!
В процессе выполнения приведенной программы многократно повторяется выполнение команд с номерами 2 и 3. Такая ситуация называется циклом.. Напомним, что цикл относится к числу основных алгоритмических структур вместе со следованием и ветвлением.
На информационной ленте машины Поста расположен массив из N меток. Каретка находится под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы?
2
3
4
4 ? 5,2
6
6 V 7
7 !
«Игра Баше»
Правила игры:
Играют двое. Перед ними 21 (или 16, или 11 и т. д.) фишка. Игроки берут фишки по очереди. За один ход можно взять от 1 до 4 фишек. Проигрывает тот, кто забирает последнюю фишку.
Имеется выигрышная тактика для игрока, берущего фишки вторым. Она заключается в том, чтобы брать такое количество фишек, которое дополняет число фишек, взятых соперником на предыдущем ходе, до пяти.
Роль фишек на информационной ленте машины Поста будут выполнять метки (знаки). Машина играет с человеком. Человеку предоставляется возможность стирать метки (брать фишки) первым. Машина будет вступать в игру второй. Исходная обстановка: на ленте массив из 21 клетки содержит метки. Каретка установлена на крайней слева клетке этого массива. Стирать метки можно только подряд. Выигрышным результатом должна быть одна оставшаяся метка перед очередным ходом человека.
Еще раз напомним принцип выигрышной тактики: стирать столько меток, чтобы в сумме с метками, стертыми противником за предыдущий ход, их было пять.
Программа управления машиной Поста в игре Баше против человека:
? 2, 1 машина ждет появления пустой клетки над кареткой. После хода человека делает свой ход.
3
4 эта серия команд выведет каретку на 5-ю (10-ю, 15-ю и т.д.) позицию.
5 Какой бы ход ни сделал соперник, в ней обязательно будет стоять метка.
6
7 Стирается метка в текущей клетке.
8 Шаг влево.
? 9, 6 Если клетка не пустая, то возврат к команде 6.
10 Каретка перемещается к первой помеченной клетке. После этого машина
? 9, 1 возвращается к команде 1 и ждет хода человека.
Действуя по данной программе и начиная стирать метки второй после человека, машина всегда будет выигрывать, если правильно задано начальное число меток, которое должно быть равно 5п + 1, где п — любое натуральное число. В противном случае машина может проиграть.
Задания:
Составить программу перевода информационной ленты машины Поста из начального состояния в конечное:
V
V
V
V
V
Н. С.
V
V
V
V
К. С.
Выполнить на машине Поста программу:
V 2
3
? 2, 4
5
V 6
!
V
V
V
V
Какую задачу решает исполнитель по этой программе?
Что произойдет, если начальной состояние будет иметь следующий вид:
V
V
V
V
Написать для машины Поста программу сложения двух чисел, записанных на ленте и расположенных через одну пустую клетку друг от друга. Начальное положение каретки — под пустой клеткой, отделяющее числа.
Написать для машины Поста программу вычитания двух чисел, разделенных одной пустой клеткой. Уменьшаемое не меньше вычитаемого. Начальное положение каретки — под пустой клеткой, отделяющей уменьшаемое от вычитаемого.
Указание. Стирать метки по одной у каждого числа, пока у вычитаемого не кончатся все метки.
Используя программу вычитания, проверить:
а) что получится, если уменьшаемое равно вычитаемому;
б) что получится, если уменьшаемое меньше вычитаемого.
Написать для машины Поста программу деления числа, записанного метками, на 2. Исходное число должно делиться на 2 без остатка.
Указание. Стереть каждую вторую метку; уплотнить оставшиеся метки.
Используя программу деления числа на 2:
а) проверить, что получится для числа 2;
б) модифицировать программу с учетом числа 2.
Указание. Справа от пустой клетки поставить метку, а слева стереть две метки. Так поступать до тех пор, пока слева остаются метки.
На информационной ленте машины Поста на расстоянии в п клеток друг от друга расположены две помеченные метками клетки. Начальное положение каретки — под левой из помеченных клеток. Какую работу выполнит машина Поста по программе?
1 2 3 4
2 ? 1, 3 4 ? 3, 1
Написать для машины Поста программу умножения на 2 числа, записанного метками на ленте.
Указание. Через одну пустую клетку поставить две метки, а в исходном числе стереть одну. Так поступать, пока в исходном числе остаются метки.
Задание *
Написать для машины Поста программу, проверяющую, делится ли записанное метками число на 5.
