Машина Поста
Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Машина Поста состоит из …
1. бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),
2. головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.
Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.
Тезис Поста является гипотезой. Его невозможно строго доказать, потому что в нем фигурируют, с одной стороны, интуитивное понятие “всякий алгоритм”, а с другой стороны — точное понятие “машина Поста”. Для того чтобы опровергнуть гипотезу Поста, необходимо придумать алгоритм, который невозможно записать в виде программы для машины Поста. На сегодняшний день такого алгоритма не существует.
Машина Поста очень простая вычислительная машина, способная выполнять лишь самые элементарные действия, тем не менее на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы.
Действия каретки подчинены программе, состоящей из перенумерованного набора команд (команды можно представлять как строки программы).
Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:
A K b,
где a - номер команды, K – действие каретки, b - номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
· V b - поставить метку, перейти к j-й строке программы.
· X b - стереть метку, перейти к j-й строке программы.
· <- b - сдвинуться влево, перейти к j-й строке программы.
· -> b - сдвинуться вправо, перейти к j-й строке программы.
·? a; b - если в ячейке нет метки, то перейти к a-й строке программы, иначе перейти к b-й строке программы.
·! – конец программы (стоп).
У команды «стоп» отсылки нет.
Команды машины обозначаются следующим образом:
Мы можем применить программу к текущему состоянию машины Поста, если выполнение программы не приведет к зацикливанию, т.е. рано или поздно мы выполним команду останов.
Варианты окончания выполнения программы на машине Поста:
1. Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.
2. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).
3. Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).
Достаточно лишь два различных символа (есть метка, нет метки). Любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита.
Пример работы машины Поста:
Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:
1 -> 2
2? 1;3
3 <- 4
4 V 5
5!
А процесс выполнения может быть таким:
Список недопустимых действий, ведущих к аварийной остановке машины
- попытка записать 1 (метку) в заполненную ячейку;
- попытка стереть метку в пустой ячейке;
- бесконечное выполнение (вообще говоря, это трудно назвать аварийным остановом, но бессмысленное повторение одних и тех же действий — зацикливание — ничуть не лучше вышеперечисленного).