Структура машини Поста.

Зауваження. Машина Поста, так як і машина Т’юринга є абстрактною машиною, тобто такою, яка існує тільки у нашій уяві, а не машиною фізичною.

Машина Поста складається з нескінченної стрічки, що розбита на комірки і каретки, яка рухається уздовж стрічки. Комірки (секції) мають однаковий розмір. Введемо на стрічці цілочисельну систему координат, привласнивши кожній секції ціле число, яке будемо вважати номером секції.

Рис.1

В кожній секції стрічки може бути або нічого не записано (така секція вважається порожньою), або записана мітка ( така секція вважається відміченою). Стан стрічки визначається розподілом міток по її секціям. Каретка може пересуватись вздовж стрічки ліворуч і праворуч. Коли каретка нерухома, то вона розміщена навпроти однієї секції стрічки. Інформація про те, які секції є пустими, а які відмічені і де саме розміщується в даний момент каретка створює стан машини Поста.

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

Робота машини Поста полягає у тому, що каретка переміщується уздовж стрічки друкуючи, або стираючи мітки. Ця робота відбувається згідно інструкції відповідного виду, яку називають програмою.

Кожна програма машини Поста складається з команд. Командою машини Поста будемо називати вираз, що має один з наступних шести видів:

1) команда руху праворуч:

;

2) команда руху ліворуч:

;

3) команда друку мітки:

;

4) команда стирання мітки:

;

5) команда передачі керування:

;

6) команда зупинки:

стоп.

Число , яке стоїть на початку команди, називається номером команди. Число , яке стоїть у кінці команди називають посиланням. У команді передачі керування називають верхнім посиланням, а нижнім посиланням.

Програмою машини Поста будемо називати скінченний непустий список команд машини Поста, що має наступні властивості:

1) на першому місті розміщується команда з номером 1, на другому місті

( якщо вона є ) команда з номером 2 і т.д.;

2) для кожного посилання кожної команди списку знайдеться у списку така команда, номер якої дорівнює посиланню, що розглядається;

Для наочності програми машини Поста краще записувати стовпчиком. Число команд програми називається довжиною програми.