Алгоритмическая машина Поста

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

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

Условимся обозначать головку знаком «Ñ» над обозреваемой секцией, а метку — знаком «М» снутри секции. Пустая секция никакого знака не содержит. За один такт (его именуют шагом) головка может двинуться на одну секцию на право либо на лево и поставить либо удалить метку. Работа машины Поста заключает в переходе от 1-го состояния машины к другому в согласовании с данной программкой, которая строится из отдельных команд. Любая команда имеет последующую структуру: хКу, где х — номер исполняемой команды; К — указание о выполняемом действии; у — номер последующей команды (наследника). Система команд машины включающая 6 действий, представлена в табл. 7.1.

Таблица 7.1.

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

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

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

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

Целое число k записывается на ленте машины Поста средством k + 1 последующих попорядку отмеченных секций, т.е. применяется унарная система счисления (см. п. 4.1). Примыкающие записи чисел на ленте делятся одной либо несколькими пустыми секциями. Ниже приведен пример записи чисел 0, 2 и 3.

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