Теория алгоритмов

Машина Поста

  1. Основные понятия и операции

    Одной из фундаментальных статей, результаты которой лежат в основе современной теории алгоритмов является статья Эмиля Поста (Emil Post), «Финитные комбинаторные процессы, формулировка 1», опубликованная в 1936 году в сентябрьском номере «Журнала символической логики»

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

    Например, решение уравнения 3*х+9=0 – это одна из конкретных проблем, а решение уравнения a*x+b=0 – это общая проблема, тем самым алгоритм (сам термин «алгоритм» не используется Постом) должен быть универсальным, т.е. должен быть соотнесен с общей проблемой.

    Основные понятия алгоритмического формализма Поста – это пространство символов (язык L) в котором задаётся конкретная проблема и получается ответ, и набор инструкций, т.е. операций в пространстве символов, задающих как сами операции, так и порядок выполнения инструкций.

    Постовское пространство символов – это бесконечная лента ячеек (ящиков):
    _V__VVV_V

    Каждый ящик или ячейка могут быть помечены или не помечены.

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

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

    1. пометить ящик, если он пуст;

    2. стереть метку, если она есть;

    3. переместиться влево на 1 ящик;

    4. переместиться вправо на 1 ящик;

    5. определить помечен ящик или нет, и по результату перейти на одну из двух указанных инструкций;

    6. остановиться.

    Отметим, что формулировка инструкций 1 и 2 включает защиту от неправильных ситуаций.

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

  2. Финитный 1 – процесс

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

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

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

    • набор инструкций заканчивается (за конечное количество инструкций), если выполняется инструкция (6);

    • набор инструкций задаёт финитный 1 – процесс, если набор применим, и заканчивается для каждой конкретной проблемы;

    • финитный 1 – процесс для общей проблемы есть 1 – решение, если ответ для каждой конкретной проблемы правильный (это определяется внешней силой).

  3. Способ задания проблемы и формулировка 1

    По Посту проблема задаётся внешней силой путем пометки конечного количества ящиков ленты. В более поздних работах по машине Поста принято считать, что машина работает в единичной системе счисления (0=V; 1=VV; 2=VVV; 3=VVVV), т.е. ноль представляется одним помеченным ящиком, а целое положительное число – помеченными ящиками в количестве на единицу больше его значения.

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

    Общая проблема называется по Посту 1-заданой, если существует такой финитный 1 – процесс, что, будучи, применим к n є N в качестве исходной конфигурации ящиков, он задает n-ую конкретную проблему в виде набора помеченных ящиков.

    Если общая проблема 1-задана и 1-разрешима, то, соединяя наборы инструкций по заданию проблемы, и ее решению мы получаем ответ по номеру проблемы – это и есть в терминах статьи Поста формулировка 1.

    Эмиль Пост завершает свою статью следующей фразой: «Автор ожидает, что его формулировка окажется логически эквивалентной рекурсивности в смысле Геделя — Черча. Цель формулировки, однако, в том, чтобы предложить систему не только определенной логической силы, но и психологической достоверности. В этом последнем смысле подлежат рассмотрению всё более и более широкие формулировки. С другой стороны, нашей целью будет показать, что все они логически сводимы к формулировке 1. В настоящий момент мы выдвигаем это умозаключение в качестве рабочей гипотезы. … Успех вышеизложенной программы заключался бы для нас в превращении этой гипотезы не столько в определение или аксиому, сколько в закон приро-ды».

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

    АЛГОРИТМ очевидно
    <-------

    гипотеза
    ------->    		 ПРОГРАММА ПОСТА


    ФОРМУЛИРОВКА 1

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

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

Rambler's Top100
Hosted by uCoz