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

Алгоритмическая машина Поста

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

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

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

Основные понятия алгоритмического формализма Поста следующие.

1. Пространство символов. В нем задаётся конкретная проблема и получается ответ. Символы должны входить в алфавит – конечное непустое упорядоченное множество символов S Î { s ₁ , s ₂ , s ₃ ,.. s_n }. Из символов алфавита формируются слова – конечные (возможно пустые) последовательности символов. Для слов определяется лексикографический порядок. Считается, что слово U = u ₁ u ₂ ... u_n предшествует слову V = v ₁ v ₂ ... v_n такой же длины, если существует такое 0 £ m £ n, что при всех 1 £ i < mu_i = v_i и u_m < v_m (например, для слов в алфавите {0, 1}1101 < 1110). Слова используются для представления исходных данных и отображения результатов работы.

В виде слов можно закодировать все объекты, с которыми могут работать алгоритмы. Для этого в алфавит необходимо ввести специальные символы-разделители. Например, в единичной системе счисления натуральное число 4 может быть записано как 1111, целое число –5 – как –11111, рациональное число –2/3 – как –11/111. Действительные числа можно приближенно представить конечными дробями. Последовательности чисел могут отображаться через разделители, матрицы – через разделители строк.

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

2. Набор инструкций – операций в пространстве символов. Они определяют как сами операции, так и порядок их выполнения.

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

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

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

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

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

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

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

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

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

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

Исполнителем инструкций (средством решения проблемы) является машина Поста. Она состоит из двух элементов:

· бесконечная лента – последовательность ячеек, в каждой из которых может быть записан только один символ алфавита;

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

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

1. Номер команды, начиная с 1.

2. Операция.

3. Отсылка – номер команды, которая должна выполняться следующей.

Виды операций:

· ® – перемещение ленты на одну ячейку вправо;

· – перемещение ленты на одну ячейку влево;

· s – запись символа sалфавита в текущую ячейку (прежнее содержимое ячейки пропадает);

· ? – разветвление (выполняется без перемещения головки и без записи на ленту):

где s_i – символ алфавита, N_i – номер команды, которая будет выполняться, если в текущей ячейке обнаружен символ s_i. Символы должны быть различными. Использование в команде всего алфавита не требуется.

· STOP – завершение работы машины (в поле отсылки не нуждается).

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

· среди символов, образующих исходные данные, нет пустых;

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

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

Выполнение программы начинается с первой команды. Возможные исходы ее выполнения следующие.

1. Результативная остановка при выполнении команды STOP – естественное завершение программы.

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

1. 2

2. 1 3

3. ® 4

5. 6

6. 7

STOP

Шаг

Команда

Состояние машины

2. Зацикливание (бесконечная работа).

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

Пусть P ( x ) – результат применения алгоритма Pк исходным данным x. Если Pнеприменим к x, это выражение не определено. Алгоритм Pсчитается эквивалентным алгоритму Q, если для любых исходных данных выражения P ( x )иQ ( x )либо не определены, либо равны.

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

1. От алгоритма не требуется конечности. Если его работа не завершается для некоторых исходных данных, то говорят, что он неприменим к этим данным.

2. Алгоритм может допускать безрезультатную остановку.

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

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

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

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

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

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

· если общая проблема 1-задана и 1-разрешима, то можно получить ответ по ее номеру (в терминах Поста – это формулировка 1).

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

АЛГОРИТМ

очевидно <------- гипотеза ------->

ПРОГРАММА ПОСТА ФОРМУЛИРОВКА 1

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

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

1. Композиция. Пусть даны алгоритмы Аи В. Их композиция определяется формулой:

P ( x ) = B ( A ( x ) ),

т. е. результат работы алгоритма P получается после применения алгоритма B к результатам выполнения алгоритма A.

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

2. Альтернатива. Пусть даны алгоритмы А, В и С. Альтернатива Qопределяется формулой:

если А(x ) = <пустое слово> , то Q ( x ) = B ( x ),

если А(x ) = <непустое слово> , то Q ( x ) = С( x ).

Если алгоритм Анеприменим к x, то и альтернатива Q неприменима к x.

3. Итерация. Пусть даны алгоритмы А и В.Итерация Ропределяется формулой:

если А(x ) = <пустое слово> , то P ( x ) = x, иначе

если А( B ( x ) ) = <пустое слово> , то P ( x ) = B ( x ), иначе

если А( B ( B ( x ) ) ) = <пустое слово> , то P ( x ) = B ( B ( x ) ), иначе

...

Алгоритм Вповторяется до тех пор, пока алгоритм Авырабатывает пустое слово.

Дата добавления: 2018-10-26; просмотров: 274; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!