Говорят, что формальный исполнитель А имитирует другого формального исполнителя В, если: каждому объекту, которым управляет исполнитель В, однозначно соответствует объект, которым управляет исполнитель А (имитация среды); каждому допустимому действию исполнителя В однозначно сопоставлено допустимое действие исполнителя А (имитация действий); каждая инструкция исполнителя В, приводящая его к определенному результату, соответствует инструкции для исполнителя А, исполнение которой приводит к соответствующему результату в среде исполнителя А.

Один из важнейших вопросов теоретической информатики звучит так: существует ли такой формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя?

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера ячейки.

В машине Поста в ячейках бесконечной ленты можно записывать всего два знака: 0 и 1 (ставить метку в ячейку или стирать метку). Это ограничение не влияет на ее универсальность, так как любой алфавит может быть закодирован двумя знаками. Кроме ленты, в машине Поста имеется каретка (головка чтения/записи), которая: умеет двигаться вперед, назад и стоять на месте; умеет читать содержимое, стирать и записывать 0 или 1 ; управляется программой.

В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Команды бывают шести типов: 1. записать 1 (метку), перейти к i-й строке программы; 2. записать 0 (стереть метку), перейти к i-й строке программы; 3. сдвиг влево, перейти к i-й строке программы; 4. сдвиг вправо, перейти к i-й строке программы; 5. останов; 6. если 0, то перейти к i, иначе перейти к j.

Список недопустимых действий, ведущих к аварийной остановке машины: попытка записать 1 (метку) в заполненную ячейку; попытка стереть метку в пустой ячейке; бесконечное выполнение (вообще говоря, это трудно назвать аварийным остановом, но бессмысленное повторение одних и тех же действий зацикливание ничуть не лучше вышеперечисленного).

Команды машины будем обозначать следующим образом: Шаг вправо Шаг влево V Записать отметку X Стереть отметку ? а; b Просмотреть ячейку: если в ячейке находится 0, то перейти на команду с номером a, иначе на команду с номером b ! Останов

Будем говорить, что мы можем применить программу к текущему состоянию машины Поста, если выполнение программы не приведет к зацикливанию, т.е. рано или поздно мы выполним команду останов. Пример программы, которая не применима ни к одному состоянию машины Поста: !

? 1; 3 3. X !

Тезис Поста заключается в том, что: Всякий алгоритм представим в форме машины Поста. Отсюда следует другое формальное определение алгоритма. Алгоритм (по Посту) программа для машины Поста, приводящая к решению поставленной задачи. Тезис Поста невозможно строго доказать, так же, как и тезис Тьюринга.