Работа машины Поста

Чтобы машина Поста начала работать, надо задать, во-первых, некоторую программу, а во-вторых, некоторое ее (машины) состояние, т. е. как-то расставить метки по секциям ленты (в частности, можно все секции оставить пустыми) и поставить каретку против одной из секций. Как правило, мы будем предполагать, что в начальном (т. е. в задаваемом вначале) состоянии машины каретка ставится всегда против секции с номером (координатой) нуль. При таком соглашении начальное состояние машины полностью определено состоянием ленты.

Как уже говорилось, программа является той инструкцией, на основании которой работает машина. Работа машины на основании заданной программы (и при заданном начальном состоянии) происходит следующим образом..Машина приводится в начальное состояние и приступает к выполнению первой команды программы (что значит «выполнить команду», будет объяснено ниже). Эта команда выполняется за один шаг, после чего машина приступает к выполнению той команды, номер которой (назовем его к) равен отсылке (одной из отсылок, если их две) первой команды. Эта команда также выполняется за один шаг, после чего начинается выполнение команды, номер которой равен отсылке команды с номером а. Вообще каждая команда выполняется за один шаг, а переход от выполнения одной команды к выполнению другой происходит по следующему правилу: пусть на k-м шаге выполнялась команда с номером i, тогда, если эта команда имеет единственную отсылку j, то па k-1-м шаге выполняется команда с номером j; если эта команда имеет две отсылки j₁и j₂, то на k + 1-м шаге выполняется одна из двух команд— с номером j₁ или с номером j₂ (какая именно, будет указано ниже); если, наконец, выполняющаяся на k-м шаге команда вовсе не имеет отсылки, то на k+1-м шаге и на всех последующих шагах не выполняется никакая команда: машина останавливается. Осталось объяснить, что значит выполнить команду и какая из отсылок — при наличии двух — выбирается в качестве номера следующей команды.

Выполнение команды движения вправо состоит в том, что каретка сдвигается на одну секцию вправо. Выполнение команды движения влево состоит в том, что каретка сдвигается на одну секцию влево. Выполнение команды печатания метки состоит в том, что каретка ставит метку на обозреваемой секции; выполнение этой команды возможно лишь в том случае, если обозреваемая перед началом выполнения команды секция пуста; если же на обозреваемой, секции уже стоит метка, команда считается невыполнимой. Выполнение команды стирания метки состоит в том, что каретка уничтожает метку в обозреваемой секции; выполнение этой команды возможно лишь в том случае, если обозреваемая секция отмечена; если же!!а обозреваемой секции и так кет метки, команда считается невыполнимой. Выполнение команды передачи управления с верхней отсылкой j₁и нижней отсылкой j₂ никак не изменяет состояния машины: пи одна из меток по уничтожается и не ставится, и каретка также остается неподвижной (машина делает, так сказать, «шаг па месте»); однако если секция, обозреваемая перед началом выполнения этой команды, была пуста, то следующей должка выполняться команда с номером j₁, если же эта секция была отмечена, следующей должна выполняться команда с номером j₂ (роль команды передачи управления сводится, следовательно, к тому, что каретка во время выполнения этой команды как бы «распознает», стоит ли перед ней метка, — именно это имелось в виду в предпоследней фразе § 1). Выполнение команды остановки тоже никак не меняет состояния машины и состоит в том, что машина останавливается.

Если теперь, задавшись программой и каким-либо начальным состоянием, пустить машину в ход, то осуществится один из следующих трех вариантов:

1) В ходе выполнения программы машина дойдет до выполнения невыполнимой команды {печатания метки в непустой секции или стирания метки в пустой секции); выполнение программы тогда прекращается, машина останавливается; происходит так называемая безрезультатная остановка.

2) В ходе выполнения программы машина дойдет до выполнения команды остановки; программа в этом случае считается выполненной, машина останавливается; происходит так называемая результативная остановка.

3) В ходе выполнения программы машина не дойдет до выполнения ни одной из команд, указанных в первых двух вариантах; выполнение программы при этом никогда не прекращается, машина никогда не останавливается; процесс работы машины происходит бесконечно.