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

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

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

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

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

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

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

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

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

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

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

Рис.2

- масив довжиною 3;

- три масива: довжиною 5, довжиною 1, довжиною 2.

Домовимось, що число запишемо на стрічці за допомогою масива довжиною . На попередньому малюнку показані машинні записи чисел 2,4,0 і 1.

Приклад 1.1.

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

1. 1.

2. 2. стоп.

3. стоп. 3.

Приклад 1.2.

1. Нехай початковий стан машини Поста такий, що на стрічці записаний машинний запис числа (інші секції стрічки порожні).

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

3. Написати програму, після виконання якої на стрічці буде машинний запис числа (всі інші секції стрічки будуть порожні), відбудеться результативна зупинка, після якої каретка може стояти у будь-якому місці.

1.? 6.

2. 7.?

3.? 8.

4. 9.

5. стоп. 10. стоп.

1.? 6.

2. 7.?

3.?

4.

5. стоп.

Приклад 2.

Скласти програму додавання двох чисел

Як доданки будемо розглядати тільки цілі невід’ємні числа. На стрічці будемо позначати невід’ємне число масивом довжини . На стрічці доданки будуть зображені наступним чином:

1. 5.

2. 6.?

3.? 7.

4. 8. стоп.