Состав машины Поста
Машина Поста состоит
из ленты и каретки (называемой
также считывающей и записывающей головкой).
Лента бесконечна и разделена на секции
одинакового размера — ячейки.
В каждой ячейке ленты может быть либо ничего не
записано, либо стоять метка V. Информация о том,
какие ячейки пусты, а какие содержат метки,
образует состояние ленты. Иными словами,
состояние ленты — это распределение меток по
ячейкам. Состояние ленты меняется в процессе
работы машины.
Метки в ячейке можно интерпретировать как “1”, а
отсутствие — “0”. Такое двоичное представление
информации подобно представлению,
используемому практически во всех современных
ЭВМ.