Машина Поста

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

Крім стрічки є головка читання/запису, який: уміє рухатися вперед, назад і стояти на місці; уміє читати вміст, стирати й записувати мітку; управляється програмою, у яку можуть входити в будь-якій комбінації й будь-якій кількості шість команд:

1) вправо;

2) уліво;

3) поставити мітку;

4) стерти мітку;

5) передача керування на один номер команди в програмі, якщо в поточнім гнізді є мітка; якщо мітки ні, те передача керування на інший номер команди;

6) припинення роботи.

Стан машини — це стан стрічки й положення головки читання/запису.

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

Машина Поста — це модель комп’ютера.

Машина одержала ім’я математика Є. Поста (США) і вирішує наступну проблему: якщо для рішення завдання можна побудувати машину Поста, то вона алгоритмічно розв’язна.

Машина Поста й машина Тьюринга еквівалентні по своїх можливостях. Розроблені практично в те саме час (в 1936 р.) незалежно друг від друга.

чи Можна будь-який алгоритм представити у формі машини Поста? Відповідь на це питання дається у вигляді так званого тези Поста: усякий алгоритм представимо у формі машини Поста. Це теза тому, що його неможливо довести, тому що в ньому фігурують, з одного боку, інтуїтивне поняття “усякий алгоритм”, а з іншого сторони — точне поняття «машина Поста».

Клас нормальних алгоритмів Маркова й клас алгоритмів, представлених у формі машин Поста, збігаються.