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