ПОСТРОЕНИЕ ВЫВОДОВ В СИСТЕМАХ ПОСТА

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

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

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

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

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

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

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

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

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

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

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

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