На самом деле, Пост, в отличие от Тьюринга, не пользовался термином «машина», а называл свою модель алгоритмической системой. Однако, подчеркивая единство подходов обоих авторов, принято говорить о машине Поста.

Абстрактная машина Поста состоит из бесконечной ленты, разделенной на равные секции, а также считывающе-записывающей головки. Каждая секция может быть либо пуста (т.е. в нее ничего не записано), либо заполнена (отмечена, т.е. в нее записана метка). Вводится понятие состояние ленты как информация о том, какие секции пусты, а какие отмечены. По-другому: состояние ленты – это распределение меток по секциям, т.е. это функция, которая каждому числовому номеру секции ставит в соответствие либо метку, либо знак «пусто». Естественно, в процессе работы машины состояние ленты меняется. Состояние ленты и информация о положении головки характеризуют состояние машины Поста.

Условимся обозначать головку знаком «» над обозреваемой секцией, а метку – знаком «M» внутри секции. Пустая секция никакого знака не содержит. За один такт (его называют шагом) головка может сдвинуться на одну секцию вправо или влево и поставить или удалить метку. Работа машины Поста заключается в переходе от одного состояния машины к другому в соответствии с заданной программой, которая строится из отдельных команд. Каждая команда имеет структуру xKy, где:

− x – номер исполняемой команды;

− K – указание о выполняемом действии;

− y – номер следующей команды (наследника).

Система команд машины, включающая шесть действий, представлена в таблице 1.

Таблица 1 - Система команд машины Поста

№ п/п	Команда	Запись команды	Описание действий машины
1	Шаг вправо	x→y	Сдвиг головки на одну секцию вправо
2	Шаг влево	x←y	Сдвиг головки на одну секцию влево
3	Установить метку	xMy	В обозреваемую секцию ставится метка
4	Стереть метку	xCy	Из обозреваемой секции удаляется метка
5	Передача управления		При отсутствии метки в обозреваемой секции управление передается команде y1 , при наличии – команде y2
6	Остановка	x стоп	Прекращение работы машины

Данный перечень должен быть дополнен следующими условиями:

− команда xMy может быть выполнена только в пустой секции;

− команда xCy может применяться только к заполненной секции;

− номер наследника любой команды y должен соответствовать номеру команды, обязательной имеющейся в данной программе.

Если данные условия не выполняются, происходит безрезультатная остановка машины, т.е. остановка до получения запланированного результата. В отличие от этой ситуации, остановка по команде x стоп является результативной, т.е. она происходит после того, как результат действия алгоритма получен. Кроме того, возможна ситуация, когда машина не останавливается никогда. Это происходит, если ни одна из команд не содержит в качестве последователя номера команды остановки или программа не переходит к этой команде.

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

Целое число k записывается на ленте машины Поста посредством k+1 следующих подряд отмеченных секций, т.е. применяется унарная система счисления. Соседние записи чисел на ленте разделяются одной или несколькими пустыми секциями.

Ниже приведен пример записи чисел 0, 2 и 3.

M

M

M

M

M

M

M

M

Круг вычислительных задач, решаемых с помощью машины Поста, весьма широк. Однако, как указывалось выше, на уровне элементарных шагов все сводится к постановке или удалению метки и сдвигу головки. В качестве примеров рассмотрим несколько задач, традиционно обсуждаемых при освоении машины Поста. Поскольку вид программы (последовательности команд машины) зависит от начального состояния машины, оно должно быть в явном виде указано в постановке задачи.

4. Алгоритмическая машина Тьюринга

Машина Тьюринга (Turing machine) получила свое название по имени английского математика Алана Тьюринга, предложившего в 1937 г. способ формального задания алгоритмов с помощью некоторой абстрактной машины. Суть работы сводится к следующему. Имеется потенциально бесконечная лента, разбитая на ячейки, в каждой из которых может быть записан один символ из некоторого конечного алфавита. Машина Тьюринга имеет головку чтения/записи, которая позволяет прочитать символ в текущей ячейке, записать символ в ячейку, а также сдвинуть головку влево или вправо в соседнюю ячейку. Машина работает дискретно, по тактам и на каждом такте находится в одном из возможных состояний, которых конечное число. Для каждой пары (состояние, обозреваемый символ) определена тройка (записываемый символ, движение головки, новое состояние). До начала работы машина Тьюринга находится в начальном состоянии, а головка чтения-записи обозревает на ленте самую левую непустую ячейку. Таким образом, обозревая очередной символ, машина записывает новый символ (может быть, тот же самый), сдвигает головку влево, вправо или остается на месте и переходит в новое состояние или остается в прежнем.

Машина Тьюринга состоит из трех частей: ленты, считывающей (записывающей) головки и логического устройства (рис. 1).

Лента выступает в качестве внешней памяти. Она считается неограниченной (бесконечной). Уже это свидетельствует о том, что машина Тьюринга является модельным устройством, поскольку ни одно реальное устройство не может обладать памятью бесконечного размера.

Рис. 1 - Схема машина Тьюринга

Как и в машине Поста, лента разбита на отдельные ячейки, однако в машине Тьюринга неподвижной является головка, а лента передвигается относительно нее вправо или влево.

Другим отличием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите A = {Δ, a₁ …a_n } – этот алфавит называется внешним. В нем выделяется специальный символ – Δ, называемый пустым знаком – его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.

Головка всегда расположена над одной из ячеек ленты. Работа происходит тактами (шагами). Система исполняемых головкой команд предельно проста: на каждом такте она производит замену знака в обозреваемой ячейке a_i знаком a_j . При этом возможны сочетания:

− j = i – означает, что в обозреваемой ячейке знак не изменился;

− i ≠ 0, j = 0 – хранившийся в ячейке знак заменяется пустым, т.е. стирается;