Теория алгоритмов. Машина Поста.

Машина Поста - абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой. Обе машины алгоритмически «эквивалентны» и были придуманы для уточнения понятия

«алгоритм» [1].

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

Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то  есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку [1].

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

Целью представляемой работы было показать сводимость (или же принципиальную несводимость) многомерной (многокареточной) машины Поста к одноленточной (однокареточной). Что значит показать полноту многомерной (многокареточной) машины Поста по Тьюринга [2]. Поскольку, в случае неполноты по Тьюрингу, мы получаем новую машину с новыми свойствами, которая в состоянии, вероятно, сильно упрощать алгоритмы. Классическая машина Поста является полной по Тьюрингу [3]. Таким образом, следует показать лишь сводимость к ней многомерной машины Поста.

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

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

несколько битов данных; время идет вперед дискретными шагами, а законы мира выражаются единственным набором правил [4].

Такое исследование представилось интересным также благодаря следующим причинам: схожесть систем (обе имеют бесконечное поле, возможный алфавит из 0 и 1, возможность описания правил) [5]; машина Поста с двухмерным полем и двумя каретками имеет хороший потенциал к сжатию данных; не было обнаружено исследований такого рода, проведённых кем-либо ранее.

А клеточные автоматы, в свою очередь, представляют интерес для криптографии.

Ведь сейчас появляется всё больше блочных алгоритмов шифрования на их основе.

Итак, первое, что нам придётся использовать это теорема: для любой машины Тьюринга существует машина Тьюринга, работающая на полубесконечной ленте [6]. Поскольку машина Тьюринга и Поста эквивалентны, то применим данную теорему к машине Поста.

Рис. 1. Эквивалентность двухленточной и одноленточной машины Поста

Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Поста может быть построена эквивалентная машина Поста с объявленным свойством. Во-первых, произвольно занумеруем  ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте. Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре. Наконец, изменим машину Поста, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МП встретится символ ‘*’, значит головка считывания-записи достигла границы зоны. Получим следующую карту состояний.

Рис. 2. Состояния МП при переходе к полубесконечному виду

Далее требуется перейти к многомерному полю. Для простоты рассмотрим на ограниченном отрезке.

Рис. 3. Соответствие полубесконечной МП и МП с двухмерным полем

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

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

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

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

Список литературы

1. Успенский В.А. Машина Поста / Гл. ред. физ.-мат. лит. 2-е изд., испр. М.: Наука, 1988. 96 с.
2. Brainerd W.S., Landweber L.H. Theory of Computation. Wiley, 1974. 278 p.
3. Neary T., Woods D. Four small universal / Turing machines. / Fundamenta Informaticae,

/ 91(1):123-144, / 2009.

4. Астафьев Г.Б., Короновский, А.А., Храмов, А.Е. Клеточные автоматы: Учебно- методическое пособие. Саратов: Изд–во ГосУНЦ «Колледж», 2003. 24 с.
5. Успенский В.А. Машина Поста. 2-е изд., испр. М.: Наука. Гл. ред. физ.-мат. лит., 1988. 96 с.
6. Карпов Ю.Г. Теория автоматов: СПб.: Питер, 2003. 208 с.