Системы порождающих правил для решения проблем

Управление функционированием интерпретатора

Рекомендуемая литература

Упражнения

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

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

Набор порождающих правил — это формализм, который уже использовался в теории автоматов, формальной грамматике, разработке языков программирования, прежде чем стать на службу моделированию психофизиологической деятельности [Newell and Simon, 1972] и экспертных систем [Buchanan and Feigenbaum, 1978]. В литературе по экспертным системам их иногда называют правилами "условие — действие" или "ситуация — действие". Это связано с тем, что такие правила обычно используются для представления эмпирических ассоциативных связей между данными, предъявленными системе, и действиями, которые система должна предпринять в ответ.

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

Канонические системы

Порождения — это в действительности грамматические правила манипулирования строками символов и потому их иногда называют правилами переписывания (rewrite rules). Пост изучал свойства систем правил, базирующихся на порождениях, которые он назвал каноническими системами [Post, 1943]. Каноническая система — это разновидность формальной системы, основанной на следующих компонентах:

алфавит А, из символов которого формируются строки;

некоторое множество строк, которые рассматриваются как аксиомы,

множества порождений в форме

а1$1... am$m->b1$'1...bn$'1...bn$'n.

Где

(I) каждое ai и bi; есть фиксированная строка;

(II) а1 и am, часто есть нуль;

(III) некоторые или все из ai или bi могут представлять собой нуль;

(IV) каждое $i является переменной строкой, которая также может быть нулем;

(V) каждое $i заменяется определенным $'i.

Определение канонической системы, возможно, станет более понятным, если привести пример. Пусть А — алфавит {а, b, с}, а аксиомы суть:

А, b, с, аа, bb, cc.

Тогда следующие порождения сгенерируют все палиндромы, базирующиеся на этом алфавите, приняв за отправную точку имеющиеся аксиомы:

(Р1)$->а$a (Р2) $ -> ab$ab (РЗ) $ -> с$с.

Более того, в данном случае можно проследить применение правил, которые должны привести к росту определенного палиндрома. Например, чтобы сгенерировать bacab, нужно применить Р1 к аксиоме с, а затем Р2 — к результату. Другими словами, приняв с в качестве аксиомы, можно вывести из нее теорему аса и добавить ее к имеющимся аксиомам. Затем из аса можно вывести новую теорему bacab. Обратите внимание, что эта последовательность порождений не обладает свойством коммутативности, т.е. если применять те же правила, но в ином порядке, получится совсем другой результат. Например, если к аксиоме с применить сначала правило Р2, а затем Р1, то получим abcba.

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

Отсюда следует, что любая формальная система может рассматриваться как каноническая (см., например, [Minsky, 1972, Chapter 12J). В действительности к этому нужно добавить тривиальную оговорку, что такая система может нуждаться еще в дополнительном алфавите, буквы которого будут использоваться в качестве знаков пунктуации в сложных доказательствах. Таким образом, для проверки доказательства в любой формальной системе или для того, чтобы выполнить любую эффективную процедуру, вполне достаточно способности прочесть строку символов, разделить ее на компоненты и переупорядочить (при этом, возможно, придется добавить еще какие-то символы или удалить существующие в исходной строке).

Смысл порождений