Автоматическая обработка информации

На прошлом уроке мы с вами узнали, что в 1930-х гг. были предложены две модели алгоритмических машин в теории алгоритмов: машина Тьюринга и машина Поста.

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

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

Программа – это алгоритм, который записан по строгим правилам языка системы команд исполнителя.

Язык программирования – это язык, на котором записаны команды для данного исполнителя.

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

Итак, машина Поста состоит из ленты и каретки.

Каретка – это считывающая и записывающая головка устройства. Лента, в свою очередь, бесконечна и разделена на секции (ячейки) одинакового размера. Для удобства будем располагать ленту горизонтально.

Каждая ячейка ленты может быть пустой либо отмеченной (в ней может быть записана метка). Информация о том, какие ячейки ленты пусты, а какие отмечены, образует состояние ленты. То есть, состояние ленты – это распределение меток по её ячейкам. В процессе работы машины состояние ленты меняется.

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

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

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

Сама работа машины Поста заключается в том, что каретка передвигается вдоль ленты, печатает или стирает метки. Для того, чтобы каретка выполняла действия, нужно составить алгоритм действий (программу). Можно сказать, что первоначальное состояние ленты – это исходные данные задачи, а конечное состояние – результат решения задачи.

Каждая программа машины Поста состоит из команд. Давайте их рассмотрим. Прежде всего мы должны знать, как записывается команда.

n <код операции> m

n – это порядковый номер, с которого начинается запись любой команды.

m – номер следующей выполняемой команды программы.

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

Программа машины Поста – это конечный непустой список команд, обладающий следующими свойствами:

·                   на первом месте стоит команда с номером 1, на втором – с номером 2 и так далее, тогда на k-ом месте будет стоять команда с номером k;

·                   отсылка любой из команд списка совпадает с номером некоторой (другой или той же самой) команды списка: можно сказать, что для каждой отсылки каждой команды списка найдётся в этом списке такая команда, номер которой равен рассматриваемой отсылке.

Давайте разберёмся на примере. У нас есть пример исходного состояния ленты.

Машина должна стереть метку, которая располагается слева от каретки или в текущей ячейке, и присоединить её в первую пустую ячейку справа от группы меток. Также дано текущее положение каретки.

Переходим к решению и запишем программу для решения задачи.

Итак, сначала нам нужно проверить, есть ли в текущей ячейке метка. Если да, то мы перейдём к команде 2, а если нет, то к команде 3. Это будет записано следующим образом: 1 ? 2, 3.

Исходя из первой команды, машина будет переходить ко 2 действию, если ячейка пуста. А если ячейка пуста, то нам нужно будет перейти в следующую. Для этого зададим шаг каретки вправо на 1 ячейку. Запишем такую команду: 2 ← 1. Это говорит о том, что во втором действии машина сделает шаг на 1 ячейку влево и перейдёт к 1 команде. Машина будет выполнять 1 и 2 действия до тех пор, пока ячейка не окажется заполненной.

Когда машина увидит, что в ячейке находится метка, то она из 1 команды перейдёт к 3. То есть в 3 действии мы должны стереть метку и перейти к 4 шагу. Команда будет выглядеть следующим образом: 3 ↕ 4.

Далее в 4 команде мы должны перейти на шаг влево, после чего выполнить пятую команду: 4 ← 5.

В 5 команде проверим, является ли текущая ячейка заполненной. Если ячейка не заполнена, то возвращаемся к 4 команде, а если в ней стоит метка, то переходим к 6 команде: 5 ? 4, 6.

Так как в 5 команде мы ссылаемся на 6 только в том случае, если в ячейке стоит метка, то сначала выполниться команда 4, затем 5, затем снова 4, так как, исходя из нашего примера состояния ленты, у нас идут 2 пустые ячейки. Затем машина перейдёт к 5 команде, с помощью которой проверит текущую ячейку. А вот сейчас ячейка заполненная, значит здесь она должна перейти к 6 команде, с помощью которой сделает шаг вправо на пустую ячейку и переход к 7 команде.

В 7 укажем запись метки и переход к 8 команде: 6 → 7.

Так как мы с вами выполнили всё то, что сказано в условии, в 8 команде остановим нашу программу: 8!.

Таким образом мы переместили метку справа налево к остальным.

В нашей программе несколько раз выполняются команды 1, 2, 4, 5. Такая ситуация называется циклом. Цикл в свою очередь относится к числу основных алгоритмических структур, также, как и следование и ветвление.

Эту же программу можно применить и к другому исходному состоянию ленты.

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

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

1 → 2

2 v 1

Машина сделает один шаг, а затем совершит безрезультатную остановку, так как в этой ячейке уже есть метка.

Если же мы применим следующую программу:

1 → 2

2 !

То машина сделает шаг, а затем произойдёт результативная остановка. Так как эта остановка задана программой.

Если же применить к этому же начальному состоянию следующую программу:

1 → 1

То машина будет работать бесконечна. То есть зациклиться.

А сейчас давайте решим задачу. На ленте имеется некоторое количество меток. Между метками могут быть пропуски не более одной пустой ячейки. Текущая ячейка является пустой. Написать программу для машины Поста, которая заполнит все пропуски метками.

Итак, приступим к решению.

Первой командой будет шаг вправо и переход ко второй команде, так как в условии сказано, что текущая ячейка является пустой: 1 → 2.

Во второй команде мы с вами проверим, пустая ячейка или нет. Если ячейка пустая, то перейдём к 3 шагу, а если нет, то к 1, чтобы продолжить нашу проверку: 2 ? 3, 1.

Далее в третьей команде делаем шаг вправо и переход к 4: 3 → 4.

А вот в четвёртой нам нужно проверить, является ли ячейка пустой. Так как по условию сказано, что между метками может находится только одна пустая ячейка: 4 ? 5, 6. Если клетка пустая, то мы переходим к 5 команде, в которой завершим программу: 5 !. Если же ячейка заполнена, то перейдём к 6 команде, в которой зададим шаг влево на одну ячейку, которая была пустой, и переход к седьмой команде: 6  ← 7.

В 7 команде мы ставим метку и переходим к 1: 7 v 1.

Таким образом мы с вами создали цикл, который заполняет пустые ячейки метками. А работу прекращает тогда, когда наш массив закончится. Об этом будет свидетельствовать некоторое количество пустых ячеек после него.

А сейчас давайте возьмём ленту, заполненную метками согласно условию, и проверим, правильно ли мы написали программу.

Итак, первая команда говорит о том, что каретке нужно продвинуться вправо в следующую ячейку. Затем, каретка проверяет, есть ли в этой ячейке метка. Так как мы видим, что в данном конкретном примере она есть, то снова возвращаемся к первой команде и идём ещё на одну ячейку вправо. И снова проверяем, пустая она или нет. В нашем случае она пустая, значит переходим к третьей команде, исходя из которой необходимо сделать шаг вправо на 1 ячейку и проверить её на наличие/отсутствие метки. Если ячейка пустая это говорит о том, что дальше массива нет. Но в нашем примере она заполнена, поэтому переходим к 6 команде, которая говорит о том, что нужно сделать шаг влево и перейти к 7 команде. Теперь ставим метку в ячейку и снова переходим к 1 команде. Делаем шаг вправо и переходим ко 2 команде. Проверяем ячейку. Она заполнена, поэтому снова переходим к 1 команде и делаем шаг вправо. Опять проверяем ячейку. Она не заполнена. Значит снова делаем шаг вправо и выполним 4 команду. Ячейка является заполненной. Далее идёт 6 команда, которая говорит нам вернуться влево на один шаг и перейти к 7 команде, с помощью которой мы заполняем пустую ячейку и возвращаемся к 1 команде. Снова делаем шаг вправо. Ячейка заполнена. Значит нужно выполнить 1 команду и сделать шаг вправо. Проверяем ячейку согласно 2 команде. Она пуста. Переходим к 3 команде и делаем ещё один шаг вправо. Ячейка снова пустая, поэтому переходим к 5 команде, которая говорит нам о завершении программы.

Этот алгоритм можно применить к любой ленте с исходными данными. Но только если они будут удовлетворять условию, что между метками может находиться не более одной пустой ячейки.

А сейчас пришла пора подвести итоги урока.

·                   Программа – это алгоритм, который, записан по строгим правилам языка команд исполнителя.

·                   Язык программирования – это язык, на котором записаны команды для данного исполнителя.

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