Абстрактні (тобто існують не реально, а лише в уяві) машини Посту і Тьюринга, призначені для доказів різних тверджень про властивості програм для них, були запропоновані незалежно один від одного (і практично одночасно) в 1936 р американським математиком Емілем Постом і англійським математиком Алланом Тьюрингом. Ці машини представляють собою універсальних виконавців, які є повністю детермінованими, що дозволяють «вводити» початкові дані, і після виконання програм «читати» результат. Машина Поста менш популярна, хоча вона значно простіше машини Тьюринга. З її допомогою можна вести навчання першим навичкам складання програм для ЕОМ.
Абстрактна машина Посту є безперервні стрічки, розділену на однакові клітини, кожна з яких може бути або порожній, або заповненої міткою «V», і головки, яка може переміщатися уздовж стрічки на одну клітку вправо або вліво, наносити в клітку стрічки мітку, якщо цієї мітки там раніше не було, прати мітку, якщо вона була, або перевіряти наявність в клітці мітки. Інформація про заповнених мітками клітинах стрічки характеризує стан стрічки, яке може змінюватися в процесі роботи машини. У кожен момент часу головка ( «-») знаходиться над однією з клітин стрічки і, як кажуть, оглядає її. Інформація про розташування головки разом зі станом стрічки характеризує стан машини Посту, рис. 1.16.
Мал. 1.16. Абстрактна машина Посту
Команда машини Посту має наступну структуру:
де п - порядковий номер команди, K-дія, що виконується головкою, т - номер наступної команди, яка підлягає виконанню.
Існує всього шість команд машини Посту, рис. 1.17:
Мал. 1.17. Команди машини Посту
Ситуації, в яких головка повинна завдавати мітку там, де вона вже є, або, навпаки, прати мітку там, де її немає, є аварійними (неприпустимими).
Програмою для машини Поста будемо називати непорожній список команд, такий що 1) на п-му місці команда з номером n; 2) номер т кожної команди збігається з номером будь-якої команди списку.
З точки зору властивостей алгоритмів, що вивчаються за допомогою машини Посту, найбільший інтерес представляють причини зупинки машини при виконанні програми:
1) останов по команді «стоп»; такий останов називається результативним і вказує на коректність алгоритму (програми);
2) останов при виконанні неприпустимою команди; в цьому випадку зупинка називається безрезультатним;
3) машина не зупиняється ніколи; в цьому і в попередньому випадку ми маємо справу з некоректним алгоритмом (програмою).
Будемо розуміти під початковим стан головки проти порожній клітини лівіше найлівішій мітки на стрічці.
Розглянемо реалізацію деяких типових елементів програм машини Посту.
1. Нехай задано початковий стан головки і потрібно на порожній стрічці написати дві мітки: одну в секцію під головкою, другу праворуч від неї. Це можна зробити за наступною програмою (праворуч від команди показаний результат її виконання):
Мал. 1.18. Приклад елемента програми машини Посту
2. Покажемо, як можна скористатися командою умовного переходу для організації циклічного процесу. Нехай на стрічці є запис з декількох міток поспіль і головка знаходиться над самої крайньої міткою справа. Потрібно перевести головку вліво до першої порожній позиції.
Програма буде мати наступний вигляд:
Команда умовного переходу є одним з основних засобів організації циклічних процесів, наприклад, для знаходження першої мітки праворуч (або ліворуч) від головки, розташованої над порожньою кліткою; знаходження зліва (або справа) від головки порожній клітини, якщо вона розташована над міткою і т.д.
3. Зупинимося на представленні чисел на стрічці машини Посту і виконанні операцій над ними.
Число k представляється на стрічці машини Посту йдуть підряд k + 1 мітками (одна мітка означає число «О»). Між двома числами робиться інтервал як мінімум з одним порожнім секції на стрічці. Наприклад, запис чисел 3 і 5 на стрічці машини Посту буде виглядати так:
Звернемо увагу, що використовувана в машині Посту система запису чисел є непозиционной.
Складемо програму для додавання до довільного числа одиниці. Припустимо, що на стрічці записано тільки одне число і головка знаходиться над однією з клітин, в якій знаходиться мітка, що належить цьому числу:
Для вирішення завдання можна перемістити головку вліво (або вправо) до першої порожній клітини, а потім нанести мітку.
Програма, що додає до числа мітку зліва, має вигляд:
Програма, що додає до числа мітку праворуч, має вигляд:
(Відмінність лише в напрямку руху головки в першій команді. Перевірте працездатність цих програм на будь-яких приватних прикладах).
Припустимо, що головка розташована на відстані декількох клітин зліва від числа, до якого потрібно додати одиницю. У цьому випадку програма ускладнюється. З'явиться «блок пошуку числа» - дві команди, що призводять головку в стан, розглянуте в попередньому прикладі:
Нижче - повні тексти програм, що додають одиницю зліва і справа, відповідно:
У першому випадку не потрібно переміщати головку до крайньої лівої мітці числа
4. Наведемо програму для складання цілих невід'ємних чисел а і і на машині Посту, коли головка знаходиться над числом а, а число b знаходиться правіше числа а на деяке число клітин. Ця програма реалізує наступний алгоритм: перше число поступово присувається до другого до їх злиття, а потім стирається одна мітка (інакше результат виявився б на одиницю більше правильного).
У разі більш складних початкових умов, коли невідомо, праворуч або ліворуч від головки (і на яке число клітин) знаходиться число, можна застосувати такий принцип пошуку числа: рухаючи головку вправо і вліво і відзначаючи мітками ступінь видалення головки від початкового положення, знайти число, а потім вже застосувати відому програму складання. При цьому перевіряється, чи знаходиться головка над однією з міток числа і якщо так, то завдання виконане. Інакше перевіряється, порожня чи секція праворуч від головки і наступна за нею; якщо обидві порожні, то робиться повернення головки на один крок і ставиться мітка, а потім така ж операція виконується зліва і по зазначеній доріжці головка повертається вправо і т.д. до тих пір, поки голівка не наштовхнеться на число, після чого можна застосувати раніше розглянуті вище програми:
Машину Посту можна розглядати як спрощену модель ЕОМ. Справді, як ЕОМ, так і машина Посту мають:
• неподільні носії інформації (клітини - біти), які можуть бути заповненими або незаповненими;
• обмежений набір елементарних дій - команд, кожна з яких
виконується за один такт (крок).