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

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

Например, нахождение решения уравнения Зхх + 9 = 0 — это конкретная проблема, так как в уравнении используются константы, а нахождение решения уравнения flXj + i = 0- это общая проблема, так как коэффициенты уравнения являются переменными величинами. Алгоритм должен быть универсальным, то есть должен находить решения поставленной задачи в общем виде. Отметим, что сам термин «алгоритм» не используется Э. Постом, его заменяет понятие на­бора инструкций.

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

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

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

Глава 14. Основы теории алгоритмов

Механизм чтения-записи

V

V

V V

Лента Рис. 14.1. Машина Поста

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

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

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

 

	Описание инструкции	Условное обозначение инструкции
	Пометить ячейку, если она пуста, и перейти к инструкции j	I Mj
	Стереть метку, если она есть, и перейти к инструкции^'	I Cj
	Переместиться влево на 1 ячейку и перейти к инструкции^'	I <-j
	Переместиться вправо на 1 ячейку и перейти к инструкции/	i. -*;'
	Определить, помечена ячейка или нет. Если ячейка пуста, перейти на инструкцию^, если помечена — на инструкцию^	г. -и
	Остановиться	i. стоп

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

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

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

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

14.1. Представление об алгоритмах 395

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

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

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

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

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

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

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

2.СЗ

3. стоп

4.^2

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

 

V

Рис. 14.2. Начальное состояние машины Поста

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

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

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