Конспект установочных лекций по комплексному курсу Информатика, Теория информации



КОМПЛЕКСНАЯ РАБОЧАЯ ПРОГРАММА - часть 21


Информация о том, какие секции пустые, а какие отмеченные, образует состояние ленты. Иными словами, состояние ленты - это распределение меток по ее секциям. На точном математическом языке состояние ленты - это функция, которая каждому числу (номеру секции) ставит в соответствие либо метку, либо "пусто". Состояние ленты, в процессе работы, может меняться.

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной секции ленты; говорят, что каретка обозревает эту секцию, или держит ее в поле зрения.Информация о том, какие секции пустые, а какие отмеченные и где стоит каретка, образуют состояние машины Поста.

Таким образом, состояние машины Поста слагается из состояния ленты и указания номера той секции, которую обозревает каретка.

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

Работа машины Поста состоит в том, что каретка передвигается вдоль ленты и печатает или стирает метки. Эта работа происходит по инструкции определенного вида, называемого программой. Для машины Поста возможно составление различных программ из разного числа команд, но эти команды строго определены.

Чтобы машина Поста работала, надо задать некоторую программу и некоторое состояние машины.

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

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

·               если эта команда имеет единственную отсылку j, то на (k + 1)-ом шаге выполняется команда с номером j;




Содержание  Назад  Вперед