Машина Поста.

 

В 1936 г. американский математик Эмиль Пост для уточнения понятия алгоритма использовал абстрактную математическую конструкцию, впоследствии названную машиной Поста.

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

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

 

 

 

 

		V		V	V	Бесконечная лента

	Каретка

Отмеченная секция

 

 

Конкретное состояние ленты с указанием, где расположена каретка, определяет состояние машины. С помощью каретки машина Поста может распознавать, является ли конкретная секция ленты отмеченной или пустой. Каретка может стереть метку, если она имеется в секции, может поместить метку в пустую секцию. С помощью каретки осуществляется побуквенное преобразование конкретного двоичного слова.

Задачей машины Поста является преобразование состояния информационной ленты. Такое преобразование машина осуществляет, руководствуясь алгоритмом, разработанным человеком. Поскольку машина Поста есть программно-управляемая машина, то алгоритм ее работы оформляется в виде программы.

Система команд машины Поста содержит шесть команд:

1. →b - команда, сдвига каретки вправо и переход к выполнению команды с номером b;

2. ←b - команда сдвига каретки влево и переход к выполнению команды с номером b;

3. Vb - команда записи метки в пустую секции и переход к выполнению команды b;

4. ↕b - команда стереть метку и переход к выполнению команды b;

5. ! - команда остановки;

6. ?< - команда передачи управления по содержимому обозреваемой секции. Если в обозреваемой секции имеется метка - то переход к выполнению коанды b, если в секции метки нет - то переход к выполнению команды a.

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

 

 

Исходное состояние Конечное состояние

 

1. ↕2 — стереть метку и перейти к выполнению команды номер 2.

2. →3 — сдвиг вправо на одну секцию и переход к выполнению команды номер 3. ^

3. ?< — принятие решения. Если обозреваемая секция пуста, то - переход к команде номер 2, иначе - к команде номер 4.

4. ←5 - сдвиг влево на одну секцию и переход к выполнению команды номер 5.

5. V6 – записать метку в пустую секцию и перейти к выполнению команды номер 6.

6. ! - остановка машины.

 

Приведенная программа дает некоторое представление о программировании по Посту и реализует функцию f(x)=х+1.

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