9.5. Построение выводов в системах поста

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

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

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

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

Простой переборный алгоритм последовательного построения всех конечных вычислений в произвольной системе = (A, B, V, P) можно представить следующей схемой:

1. Определим переменную d, начальное значение которой равно 1.

2. Образуем множество M, состоящее из всех слов в алфавите A  V, длина которых равна d.

3. Последовательно выписываем все возможные последовательности, состоящие из d слов множества M.

Для каждой такой последовательности W проверяется, является ли она вычислением. Если это так, то W и ее начальные фрагменты добавляется к формируемому списку всех конечных выводов в системе .

4. Увеличим значение d на 1 и повторим действия 2  4.

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

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

9.6. Свойства множеств выводимых слов

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

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

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

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

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

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

₁ = N0; ₂ = N1; ₃ = N11; ₄ = N10;

₅ = ; ₆ = .

Пары целых неотрицательных чисел (x, y) выводятся с помощью продукции:

₇ = .

Приведенная система Поста имеет основной алфавит A = {0, 1, (, ), ,} и вспомогательный алфавит V = {N}.

Результатами в такой системе являются только такие выводимые слова, которые не содержат символа N.

Выводимые в системе вспомогательные слова имеют вид Nx.

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

Слова из первого класса называются нетерминальными словами системы Поста; из второго класса  терминальными, или заключительными.

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

Рассмотрим ещё один пример системы Поста, в которой выводятся все возможные пары слов вида ( , ), где  это произвольная последовательность из нулей и единиц, а  двоичная запись числа, равного длине последовательности .

Выпишем множество продукций соответствующей системы Поста.

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

₁= N1; ₂= N0; ₃= N11; ₄ =N10; ₅: ; ₆: .

2. Вспомогательные продукции, позволяющие выводить слова вида S(x) = y, где x и y  это правильные двоичные записи неотрицательных целых чисел и у = x + 1:

₇: S( 0 ) = 1; ₈: ; ₉: .

3. Основные продукции, позволяющие выводить пары, слов ( , ), которые являются заключительными:

₁₀: (0 , 1); ₁₁: (1, 1);

₁₂: ; ₁₃: .

Здесь символы N и S образуют вспомогательный алфавит, а x, y, z  алфавит переменных. Остальные символы составляют основной алфавит.

Упражнение. Привести пример множества слов в алфавите {0, 1}, которое выводится только в таких системах Поста, которые имеют непустой вспомогательный алфавит.

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

Справедливость приведенного свойства вытекает из теоремы 9.2.

ТЕОРЕМА 9.2

Если ₁ и ₂  множества слов, выводимых в системах ₁ и ₂ соответственно, то найдутся такие системы _U и _I, в которых выводятся соответственно множества

₁  ₂ и ₁₂.

Доказательство

Пусть R и Q  символы, которые не встречаются среди символов алфавитов систем ₁ и ₂.

1. Определим систему _U. Основной алфавит и алфавит переменных этой системы получаются объединениями основных алфавитов и алфавитов переменных систем ₁ и ₂.

Вспомогательный алфавит системы _U состоит из символов вспомогательных алфавитов для ₁ и ₂, а также символов R и Q.

Множество продукций системы _U состоит из продукций, получаемых из продукций ₁ приписыванием всем образцам слева символа R, а также продукций, получаемых из продукций системы ₂ с помощью аналогичного приписывания символа Q.

Кроме того, в _U добавлены продукции:

и .

Покажем, что в системе _U выводятся те и только те слова, которые принадлежат ₁ _2.

Это следует из того, что некоторое слово x выводится в системе _U тогда и только тогда, когда в этой системе выводится либо слово Rx, либо слово Qx.

Последнее равносильно тому, что x выводится либо в ₁, либо в ₂. Поэтому в _U выводится множество слов ₁ ₂.

2. Определим систему Поста _I.

Алфавиты этой системы определяются так же, как это было определено для системы P_U.

Продукции системы _I получаются из продукций ₁ и ₂ приписыванием ко всем образцам в них слева символов R и Q соответственно.

К этим продукциям добавляется еще одна

.

Видно, что в системе _I выводятся такие и только такие слова x, которые могут быть выведены как в _1, так и в ₂.

Поэтому множество слов, выводимых в системе _I, равно ₁ ₂.

Доказательство окончено.

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

Если, например, при построении системы _U в качестве множества продукций для _U взять объединение множеств неизмененных продукций систем ₁ и ₂, то можно получить систему, в которой выводятся слова, не входящие в ₁ ₂.

В качестве примера рассмотрим системы ₁ и ₂ со следующими совокупностями продукций:

_1,1: 1, _1,2: ; (1)

_2,1: 0, _2,2: . (2)

Тогда с помощью продукций (1) системы ₁ можно выводить слова, составленные только из единиц, а при помощи множества (2) системы ₂  слова, которые имеют конечное число нулей.

Однако продукции _1,1, _1,2, _2,1, _2,2, используемые совместно, позволяют выводить любые слова, состоящие из нулей и единиц.

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

Это означает, что существует такая система  = (A,B,V,P), для которой множество A* \ _ не выводится ни в одной системе Поста. Доказательство этого факта будем приведено ниже после изучения связи множеств слов, выводимых в системах Поста и множества частично-рекурсивных функций.

Всякое множества   таких слов в некотором основном алфавите A, что  и его дополнение до A* выводимы в некоторых системах Поста, является разрешимым.

Справедливость последнего свойства вытекает из следующей теоремы.