Ідея машини полягає у тому, що:
1) алгоритмічні процеси є послідовністю досить простих «механічних» операцій;
2) на результат не впливає, хто виконує алгоритм і скільки разів, — він завжди один і той самий;
3) отже, алгоритмічні процеси може виконувати машина.
Таким чином, можна винайти машину, яка вміє виконувати певний набір операцій. Яких? Якою повинна бути сукупність операцій, щоб можна було реалізувати або імітувати будь-які алгоритмічні процеси?
В гіпотетичній (умовній) машині Поста (1936 р.) інформацію представляють у двійковому алфавіті А = {1,0}. Вона має інформаційну стрічку необмеженої довжини — пам’ять машини. Стрічка поділена на окремі комірки. В кожній комірці можна розмістити 0 або 1.
Машина має «зчитувальну головку» (спеціальний чутливий елемент), яка оглядає зміст однієї комірки. Інформаційна стрічка переміщується в обидва боки так, щоб у кожний момент часу головка знаходилась навпроти однієї певної комірки стрічки.
Машина має керуючий пристрій, який у кожний момент часу перебуває у певному стані. Таких станів є скінченна множина. Один із таких станів є заключним і керує завершенням роботи машини.
q j
Керуючий пристрій знаходиться у стані q, «зчитувальна головка» оглядає j-ту комірку.
Машина може виконувати певний перелік правил (або наказів). Машина Поста може виконувати 6 типів наказів:
1. Записати у розглядувану комірку 1 та перейти до i-го наказу.
2.Записати у розглядувану комірку 0 та перейти до i-го наказу.
3. Зсунути стрічку праворуч на 1 комірку та перейти до i-го наказу.
4. Зсунути стрічку ліворуч на 1 комірку та перейти до i-го наказу.
5. Якщо у розглядуваній комірці записано 1, то перейти до i-го наказу, а якщо 0 — то перейти до j-го наказу.
6. Останов. Закінчення роботи алгоритму.
Алгоритми, побудовані з будь-якого скінченного числа правил машини Поста, називають алгоритмами Поста. Вони можуть бути зведені до алгоритмів, побудованих у системі рекурсивних функцій (і навпаки).
