На самом деле, Пост, в отличие от Тьюринга, не пользовался термином «машина», а называл свою модель алгоритмической системой. Как принято в литературе, все же будем говорить о машине Поста, подчеркивая тем самым единство подходов обоих авторов [41].
Абстрактная машина Поста состоит из бесконечной ленты, разделенной на равные секции, а также считывающе-записывающей головки. Каждая секция может быть либо пуста (т.е. в нее ничего не записано), либо заполнена (отмечена - т.е. в нее записана метка). Вводится понятие состояние ленты как информация о том, какие секции пусты, а какие отмечены (по-другому: состояние ленты - это распределение меток по секциям, т.е. это функция, которая каждому числовому номеру секции ставит в соответствие либо метку, либо знак «пусто»). Естественно, в процессе работы машины состояние ленты меняется. Состояние ленты и информация о положении головки характеризуют состояние машины Поста.
Условимся обозначать головку знаком «Ñ» над обозреваемой секцией, а метку - знаком «М» внутри секции. Пустая секция никакого знака не содержит. За один такт (его называют шагом) головка может сдвинуться на одну секцию вправо или влево и поставить или удалить метку. Работа машины Поста заключает в переходе от одного состояния машины к другому в соответствии с заданной программой, которая строится из отдельных команд. Каждая команда имеет следующую структуру: хКу, где х - номер исполняемой команды; К - указание о выполняемом действии; у - номер следующей команды (наследника). Система команд машины включающая шесть действий, представлена в табл. 7.1.
Таблица 7.1.
Данный перечень должен быть дополнен следующими условиями:
· команда <хМу> может быть выполнена только в пустой секции;
· команда <хСу> может применяться только к заполненной секции;
· номер наследника любой команды (у) должен соответствовать номеру команды, обязательной имеющейся в данной программе.
Если данные условия не выполняются, происходит безрезультатная остановка машины, т.е. остановка до получения запланированного результата. В отличие от этой ситуации, остановка по команде <х стоп> является результативной, т.е. она происходит после того, как результат действия алгоритма получен. Кроме того, возможна ситуация, когда машина не останавливается никогда - это происходит, если ни одна из команд не содержит в качестве последователя номера команды остановки или программа не переходит к этой команде.
Еще одним исходным соображением является следующее: поскольку знаки любого конечного алфавита могут быть закодированы цифрами, преобразование исходного слова может быть представлено в виде некоторых правил обработки чисел. По этой причине в машине Поста предусматривается только запись (представление) целых положительных чисел.
Целое число k записывается на ленте машины Поста посредством k + 1 следующих подряд отмеченных секций, т.е. применяется унарная система счисления (см. п. 4.1). Соседние записи чисел на ленте разделяются одной или несколькими пустыми секциями. Ниже приведен пример записи чисел 0, 2 и 3.
Круг вычислительных задач, решаемых с помощью машины Поста, весьма широк. Однако как указывалось выше, на уровне элементарных шагов все сводится к постановке или удалению метки и сдвигу головки. В качестве примеров рассмотрим несколько задач, традиционно обсуждаемых при освоении машины Поста. Поскольку вид программы (последовательности команд машины) зависит от начального состояния машины, оно должно быть в явном виде указано в постановке задачи.