Главная (Машина Поста) Проверка знаний

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера: для наглядности ленту располагают горизонтально.

lenta1.gif
Бесконечность ленты не позволяет реализовать машину Поста физически. Лента объявляется бесконечной для простоты.
Порядок, в котором расположены секции ленты, подобен порядку, в котором расположены все целые числа. Поэтому естественно ввести на ленте "целочисленную систему координат", занумеровав секции целыми числами ..., -3, -2, -1, 0, 1, 2, 3,... .
lentanumb
Считается, что система координат жестко сопоставлена с лентой, и получим таким образом возможность указывать какую-либо секцию ленты, называя ее порядковый номер или координату. (Хотя для удобства, наряду с основной, вводят "временную" систему координат.) В каждой секции ленты может быть либо ничего не записано (такая секция называется пустой), либо записана метка V (тогда секция называется отмеченной).
checked
Информация о том, какие секции пусты, а какие отмечены, образует состояние ленты. Иными словами, состояние ленты - это распределение меток по ее секциям (на точном математическом языке состояние ленты - это функция, которая каждому числу (номеру секции) ставит в соответствие либо метку, либо, скажем, слово "пусто".) В процессе работы машины состояние ленты меняется.
Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против одной секции ленты:
caret1
Ситуация на рисунке ниже может возникнуть только в процессе движения:
caret2
Когда каретка стоит против одной из секций, то говорят, что каретка обозревает эту секцию, или держит ее в поле зрения. Информация о том, какие секции пусты, а какие отмечены и где стоит каретка, образует состояние машины Поста. Таким образом, состояние машины слагается из состояния ленты и указания номера той секции, которую обозревает каретка. За единицу времени, которую называют шагом, каретка может сдвинуться на одну секцию влево или вправо. Кроме того, каретка может поставить (напечатать) или уничтожить (стереть) метку в той секции, против которой она стоит, а также распознать, стоит или нет метка в обозреваемой ею секции.
Работа машины Поста состоит в том, что каретка передвигается вдоль ленты и печатает или стирает метки. Эта работа происходит по инструкции определенного вида, называемой программой.
Каждая программа машины Поста состоит из команд. Командой машины Поста называется выражение, имеющее один из следующих шести видов (буквы i, j, j1, j2 означают всюду натуральные числа 1, 2, 3, 4, 5, ...): Число i, стоящее в начале команды, называется номером команды. Число j, стоящее в конце команды (а у команд передачи управления - каждое из чисел j1, j2), будем называть отсылкой (при этом в команде передачи управления j1 - верхней, а j2 - нижней отсылкой). У команд остановки нет отсылки.
Программой машины Поста будем называть конечный непустой (т.е. содержащий хотя бы одну команду) список команд машины Поста, обладающий следующими двумя свойствами:
  1. На первом месте в этом списке стоит команда с номером 1, на втором месте (если оно есть) - команда с номером 2 и т.д.; вообще на k-ом месте стоит команда с номером k.
  2. Отсылка любой из команд списка совпадает с номером некоторой (другой или той же самой) команды списка (более точно: для каждой отсылки каждой команды списка найдется в списке такая команда, номер которой равен рассматриваемой отсылке).
Пример. Следующий список является программой машины Поста:
  1. стоп
  2. comprim
  3. C 3
  4. стоп
Для наглядности программы их записывают столбиком. Число команд программы называется длиной программы.
Вверх

Дубровка Евгений, МФ ПМ 1 курс, 2002