МАШИНА ПОСТА

Машина Поста (МП) — абстрактна обчислювальна машина, запропонована Эмилем Л. Постом (Emil L. Post), яка відмінна від машини Тюрінга більшою простотою. Обидві машини «еквівалентні» і були створені для уточнення поняття «алгоритм».

Принцип роботи

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

N.   →   J рух вправо
N.   ←   J рух вліво
N.   1   J запис мітки
N.   0   J видалення мітки
N.   ? J1, J0   умовний перехід по мітці
N.   Stop Зупинка

де N – номер строчки, J – строчка на яку переходить керування далі.

Для роботи машини потрібно задати програму і її початкові стани (тобто стани стрічки і позицію каретки). Після запуску можливі варіанти:

  • робота може закінчитись невиконуваною командою (видалення неіснуючої мітки чи запис в помічене поле);
  • робота може закінчиться командою Stop;
  • робота ніколи не закінчитись.

Приклад: віднімання натуральних чисел P — Q

Будемо представляти натуральне (ціле невід’ємне) число P набором з P+1 одиниць і розділяти числа нулем. Вихідне положення каретки помічено символом «v»

            v
    00111110111000
        P    Q

Додавання двох чисел дуже просто – достатньо поставить 1 між ними і видалити крайній правий символ у Q. Програма віднімання складається з послідовного затирання крайніх лівих міток у Q і правих у P:

1. 0       - стираємо лівий символ у Q
2. →
3. ? 5, 4
4. Stop    - стоп якщо затерли Q=0
5. ←
6. ? 7, 5  - цикл пошуку P
7. 0       - стираємо правий символ у P
8. →
9. ? 1, 8  - шукаємо Q


завантаження...
WordPress: 22.85MB | MySQL:26 | 0,331sec