Машина Поста

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

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

• неподільні носії інформації (комірки — біти), які можуть бути заповненими або незаповненими;
• обмежений набір елементарних дій — команд, кожна з яких виконується за один такт (крок).

Обидві машини працюють на основі програми. Проте у машині Поста інформація розташовується лінійно і читається підряд, а в комп'ютері можна читати інформацію за адресою; набір команд комп'ютера значно ширший і виразніший за команди машини Поста.

Склад машини Поста

Машина Поста складається із стрічки та каретки (яка також називається головкою зчитування/запису). Стрічка є безмежною і розділена на комірки однакового розміру. Комірка стрічки може бути порожньою, або у ній може перебувати мітка V. Інформація про те, які комірки порожні, а які містять мітки, утворює стан стрічки. Іншими словами, стан стрічки — це розподіл міток по комірках. Стан стрічки змінюється у процесі роботи машини. Зауважимо, що наявність міток у комірці можна інтерпретувати як «1», а відсутність як «0». Таке двійкове представлення інформації подібне до уявлення, яке використовується практично у всіх сучасних комп'ютерах.

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

1. записати 1 (мітку), перейти до i-го рядка програми;
2. записати 0 (стерти мітку), перейти до i-го рядка програми;
3. переміститися вліво, перейти до i-го рядка програми;
4. переміститися вправо, перейти до i-го рядка програми;
5. зупинитися;
6. якщо 0, то перейти до i-го рядка програми, інакше перейти до j-го рядка програми.

Наведемо перелік неприпустимих дій, які ведуть до аварійної зупинки машини:

• спроба записати 1 (мітку) в заповнену комірку;
• спроба стерти мітку в порожній комірці;
• нескінченне виконання (зациклення).

Програма Поста

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

• команда зміщення праворуч: i → j
• команда зміщення ліворуч: i ← j
• команда встановлення мітки: i j j
• команда знищення мітки: i ε j
• команда передачі керування: i ?→ j1, j2
• команда зупинки: i стоп або і ! (знак оклику)

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

• на n-му місці записується команда з номером N;
• передача керування повинна відбуватися тільки до існуючого номеру команди.

Необхідні умови роботи машини Поста

• визначеність стану машини Поста (місцерозташування каретки і міток);
• наявність програми машини Поста.

Зауваження щодо роботи машини Поста

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

Результат виконання програми машини Поста

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

Примітки

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

Графічне представлення команд машини Поста

n.   →   m	Крок вправо
n.   ←   m	Крок вліво
n.   V   m	Записати мітку
n.   X   m	Стерти мітку
n.   ? a: b	Переглянути комірку: якщо в комірці знаходиться 0, тоді перейти на команду з номером а, інакше на команду з номером b.
n.   !	Зупинка

Будемо розуміти, що ми можемо застосувати програму до біжучого стану машини Поста, якщо виконання програми не призведе до зациклювання, тобто рано чи пізно ми виконаємо команду «Зупинка».

Програмою для машини Поста називається непорожній список послідовно пронумерованих команд наступної структури: n K m, де n — порядковий номер команди, K − дія, яка виконується кареткою, m — номер наступної команди, яку необхідно виконати.

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

• зупинка за командою «стоп». Така зупинка називається результативною і вказує на коректність алгоритму;
• зупинка при виконанні неприпустимої команди. У цьому випадку зупинка називається безрезультатною;
• машина не зупиняється ніколи. У цьому і у попередньому випадку ми маємо справу з некоректним алгоритмом.

Під початковим станом каретки розумітимемо її положення навпроти порожньої комірки лівіше за найлівішу мітку на стрічці.

Приклад 1

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

Розв'язок. Спочатку спробуємо описати алгоритм звичайною мовою. Оскільки нам відомо, що каретка стоїть навпроти порожньої комірки, але невідомо, скільки кроків потрібно зробити до заповненої комірки, ми можемо відразу зробити крок вправо; перевірити, чи заповнена комірка; якщо вона порожня, то повторювати ці дії доти, поки не наштовхнемося на заповнену комірку. Щойно ми її знайдемо, ми виконаємо операцію стирання, після чого потрібно буде лише змістити каретку вліво і зупинити виконання програми. Програма пошуку і стирання єдиної мітки на стрічці для машини Поста має такий вигляд:

1. → 2
2.  ? 1: 3
3. X 4
4. ← 5
5.  !

Приклад 2

На стрічці заданий масив міток. Збільшити довжину масиву на 2 мітки. Каретка знаходиться або зліва від масиву, або над однією з комірок масиву.

Розв'язок.

1.  ? 2: 3 (команди 1 і 2 — пересуваємо каретку до масиву)
2. → 1
3. → 4 (команди 3 і 4 — пересуваємо каретку до кінця масиву)
4.  ? 5: 3
5. V 6 (команди 5–7 — ставимо 2 мітки в кінець масиву)
6. → 7
7. V 8
8.  ! (стоп)

Приклад 3

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

1. X 2
2. → 3
3.  ? 4: 2
4. V 5
5. → 6
6.  ? 8; 7
7.  !
8. ← 9
9.  ? 10: 8
10. → 1

Див. також

• Машина Тюрінга

Джерела

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• Роджерс Х.(інші мови). Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
• С. М. Прийма «Теорія алгоритмів і математична логіка»
• Навчальні матеріали з інформатики " Основні поняття інформатики " Машина Поста [Архівовано 29 травня 2014 у Wayback Machine.]