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

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

1) деяку програму;

2) деякий стан машини ( тобто розставити мітки по секціях стрічки і поставити каретку навпроти однієї із секцій);

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

нехай на -ому кроці виконується команда з номером . Тоді, якщо ця команда має одне посилання , то на -ому кроці виконується команда з номером . Якщо ця команда має два посилання , то на -ому кроці виконується команда з номером , якщо секція, яку оглядала каретка на -ому кроці була пустою, і , якщо була відмінною. Виконання команди руху праворуч полягає у тому, що каретка переміщується на одну секцію праворуч. Виконання команди руху ліворуч полягає у тому, що каретка переміщується на одну секцію праворуч. Виконання команди друку мітки полягає у тому, що каретка ставить мітку у секції, яку вона оглядає у поточний момент часу. Виконання команди витирання мітки полягає у тому, що каретка ліквідує мітку у секції, яку вона оглядає у поточний момент часу.

Висновок. Якщо, маючи програму та початковий стан, запустити машину Поста та відбудеться один з трьох варіантів.

1. У ході виконання програми машина спробує виконати команду, виконання якої є неможливим (друк мітки у секції, яка уже є відміченою, або витирання мітки у секції, яка є порожньою). У цьому випадку виконання програми припиняється – це називається безрезультатною зупинкою.

2. У процесі виконання програми машина дійде до виконання зупинки. Програма у цьому випадку вважається виконаною, машина зупиняється – це називається результативною зупинкою.

3. У процесі виконання програми машина ніколи не дійде до виконання жодної з команд, що зазначені у пунктах 1 і 2. Виконання програми при цьому ніколи не припиняється, машина працює нескінченно довго.

Будемо розглядати цілі невід’ємні числа (0,1,2,…). Розглянемо скінченну послідовність відмічених підряд секцій стрічки, що розміщена між двома порожніми секціями. Таку послідовність відмічених секцій будемо називати масивом, а число секцій у ній – довжиною масива.

Рис.2