Формализация понятия алгоритма посредством машины Поста

Пост рассматривает общую проблему, состоящую из множества конкретных проблем, при этом решением общей проблемы является такое решение, которое определяет ответ для конкретной проблемы.

Например, нахождение решения уравнения – это конкретная проблема, так как в уравнении используются константы, а нахождение решения уравнения – это общая проблема, так как коэффициенты уравнения являются переменными величинами. Алгоритм должен быть универсальным, то есть должен находить решения поставленной задачи в общем виде. Отметим, что сам термин «алгоритм» не используется Э. Постом, его заменяет понятие на бора инструкций.

Машина Поста представляет собой абстрактный механизм для выполнения алгоритмов. Этот механизм состоит из двух узлов (рисунок 13.1):

- бесконечной ленты, разделенной на ячейки, каждая из которых может быть помечена или не помечена меткой V;

- механизма чтения-записи (в дальнейшем – каретка), который может перемещаться вдоль ленты вправо и влево, записывать метку в пустую ячейку, стирать метку в помеченной ячейке и проверять наличие метки в ячейке.

Рисунок 13.1 – Машина Поста

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

Пост в 1936 г. предложил набор инструкций, или элементарно выполнимых операций, которые выполняет «работник». В терминах современного состояния компьютерной области этот набор инструкций можно трактовать как минимальный набор битовых операций элементарного процессора. В таблице 13.1 приведены инструкции машины Поста. Латинскими буквами i, j, j ₁, j ₂,и т. д. обозначены номера инструкций; М – пометить ячейку, С – стереть метку.

Таблица 13.1 – Инструкции машины Поста

№	Описание инструкции	Условное обозначение инструкции
	Пометить ячейку, если она пуста, и перейти к инструкции	i, Mj
	Стереть метку, если она есть, и перейти к инструкции	i, Cj
	Переместиться влево на 1ячейку и перейти к инструкции	i, ß j
	Переместиться вправо на 1 ячейку и перейти к инструкции	i, à j
	Определить, помечена ячейка или нет. Если ячейка пуста, перейти на инструкцию , если помечена – на инструкцию
	Остановиться	i, стоп

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

Далее Э. Пост вводит следующие понятия:

- набор инструкций применим к общей проблеме, если для каждой конкретной проблемы не возникает коллизий в инструкциях 1 и 2, то есть программа никогда не стирает метку в пустой ячейке и не устанавливает метку в помеченной ячейке;

- набор инструкций заканчивается, если после конечного количества инструкций выполняется инструкция 6.

Начальное состояние машины Поста полностью определяется двумя факторами: положением каретки (на какой из ячеек она находится) и состоянием ленты (наличием на ленте помеченных ячеек).

В зависимости от начального состояния машины Поста могут быть три варианта выполнения одной и той же программы:

1. В ходе выполнения программы машина доходит до невыполнимой инструкции (печатания метки в непустой ячейке или стирания метки в пустой ячейке). Происходит безрезультатная остановкамашины.

2. В ходе выполнения программы машина доходит до инструкции Стоп. Происходит результативная остановка.

3. Работа машины продолжается бесконечно.

Машина Поста оперирует натуральными числами, которые представляются в непозиционной системе счисления (то есть 0 обозначается одной помеченной ячейкой, 1 – двумя идущими подряд помеченными ячейками, и т. д.). В общей форме натуральное число п представляется п + 1 смежными помеченными ячейками.

Пример. Рассмотрим следующую программу для машины Поста:

1.

2. С 3

3. стоп

4.

Зададим такое начальное состояние машины, которое показано на рисунок 13.2.

Рисунок 13.2 – Начальное состояние машины Поста

Поскольку каретка находится на пустой ячейке, первая команда программы вызывает переход на команду с номером 4, При этом каретка не меняет своего положения, и состояние ленты также не меняется (метка не ставится и не стирается).

Команда с номером 4 вызывает перемещение каретки на одну позицию вправо (теперь каретка находится на помеченной ячейке) и передачу управления команде 2.

Команда 2 стирает метку в текущей ячейке и передает управление команде 3. Команда 3 останавливает работу машины.

Дата добавления: 2013-12-13