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

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

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

-5	-4	-3	-2	-1

Рис.1

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

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

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

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

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

;

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

;

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

;

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

;

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

;

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

стоп.

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

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

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

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

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

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