Определение

Продукционной системой (системой Поста) называется тройка  = (A, B, V, P), в которой A и B  основной и вспомогательный алфавиты, V  алфавит переменных, а P  конечная совокупность продукций в этих алфавитах.

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

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

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

Смысл продукции системы поясняется по мере их перечисления.

Аксиомы

1. Правила получения значения младшего разряда суммы одноразрядных десятичных чисел:

0 + 0 = 0 , . . . , 0 + 9 = 9;

1 + 1 = 1 , . . . , 1 + 9 = 0;

. . .

9 + 0 = 9 , . . . , 9 + 9 = 8.

2. Правила получения значения переноса в старший разряд при сложении двух одноразрядных чисел (если сумма таких чисел одноразрядная, то считаем его равным 0):

0 + 0 = 0s, . . . , 0 + 9 = 0s;

1 + 1 = 0s, . . . , 1 + 9 = 1s;

. . .

9 + 0 = 0s, . . . , 9 + 9 = 1s.

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

3. Специальные аксиомы:

x + 0 = x;

x + y = y+x.

Эти аксиомы формулируются в предположении, что x и y представляют собой числа.

4. Продукция-неаксиома

Правило сложения двух десятичных чисел:

 = .

По последнему правилу можно найти сумму двух произвольных чисел, записываемых как ux и wy, где x и y  младшие разряды десятичных записей чисел, если выполнены (или вычислены) соотношения, являющиеся посылками продукции:

a) значение младшего разряда суммы равно t (может быть взято из соответствующей аксиомы);

б) значение переноса при сложении младших разрядов равно z (также берется из аксиомы);

в) значение суммы чисел u и w вместе со значением переноса z равно k.

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

Тогда соответствующая система Поста имеет вид = (A, B,V, P), где P  это приведенные продукции, а

A = { +, =, s, 0, . . . , 9}, B =  и V = { x, y, z, v, w, k, t}.

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

9.2. Вычисления в системах поста

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

Определение

Выводом в системе Поста  = (A, B, V, P) называется всякая последовательность слов в алфавите A  B, каждый элемент которой либо является применением одной из аксиом из P, либо получается применением одной из продукций множества P к словам, которые уже вошли в вывод.

Слово  A* называется выводимым в системе Поста , если в этой системе можно определить вывод, содержащий .

Множество всех слов, выводимых в системе , обозначается как .

Длиной вывода называется число входящих в него слов.

В системах Поста возможны как конечные, так и бесконечные выводы.

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

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

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