Машина Поста: фундаментальна модель обчислень
Машина Поста — це абстрактна обчислювальна конструкція, що складається з нескінченної в обидва боки стрічки. Стрічка розділена на комірки, кожна з яких послідовно пронумерована цілими числами (додатними та від’ємними). Кожна комірка може бути або порожньою, або містити мітку (V). Сукупність заповнених і порожніх комірок визначає стан стрічки.
Крім стрічки, машина має каретку (головку зчитування/запису). Вона може:
- пересуватися вліво або вправо на одну комірку;
- зчитувати вміст комірки;
- ставити або стирати мітку.
Роботою каретки керує програма, що складається з довільної комбінації шести команд:
- Вправо: рух до сусідньої комірки праворуч.
- Вліво: рух до сусідньої комірки ліворуч.
- Поставити мітку: запис символу в поточну комірку.
- Стерти мітку: очищення поточної комірки.
- Умовний перехід: якщо в комірці є мітка, виконується одна команда програми, якщо немає — інша.
- Стоп: припинення роботи.
Стан машини — це поєднання стану стрічки та положення каретки. Попри зовнішню простоту, машина Поста здатна виконувати будь-які обчислення. Для цього достатньо задати початковий стан і відповідний алгоритм.
Історія та значення Модель розробив американський математик Еміль Пост у 1936 році, практично одночасно та незалежно від Алана Тьюринга. Машини Поста й Тьюринга еквівалентні за своїми можливостями.
Відповідь на питання «Чи можна подати будь-який алгоритм у формі машини Поста?» дає так звана теза Поста: будь-який алгоритм можна реалізувати на цій машині. Це твердження є тезою, а не теоремою, оскільки воно пов’язує інтуїтивне поняття «алгоритм» із точним математичним поняттям «машина Поста». Доведено, що класи алгоритмів Маркова, Тьюринга та Поста повністю збігаються за своєю обчислювальною потужністю.