Production Systems and Formal Systems

• A production system has 3 components:
• A set of rules
• A working memory, hereafter called WM
• An algorithm for applying the rules to the contents of working memory
• A formal system has 2 components:
• A set of rules
• A set of axioms
A production system, therefore is a special case of a formal system, where the axioms are the initial content of WM, and where we have a fixed system for choosing which rules to apply to which axioms.

Rules

There are many, many ways to write rules. They are all roughly equivalent. They have a left hand side (also called the antecedent) and a right hand side (also called the consequent). Consider the rule, which we will informally state as "If WM contains a sequence which ends with the symbol I, then add on a U to that sequence". So if WM has any of the following sequences:
1. MI
2. UUIIMMIII
3. III
Then we could produce any of the following sequences:
1. MIU
2. UUIIMMIIIU
3. IIIU
This rule could have been written in any of the following ways (the list is not exhaustive!):
• IF(*I) THEN(*IU)
• *I -> *IU
• NULL -> U / I_#
• ```  (if
((ends-with-i ?string))
(then
```
Rules may be domain specific or domain general. A domain specific rule might be, e.g., "If two notes are of the same pitch, then group them together". A more general rule would then be "If things are similar then group them together".

A simple formal system

This system was invented by Douglas Hofstadter, and is described in "Goedel, Escher, Bach", which is highly recommended reading! I have altered it only slightly.

This system, the pq system, is very simple. There are only 3 symbols in this world:

p,q, and -
There is only one rule too:
Let ?x, ?y, and ?z all be strings of hyphens. If ?xp?yq?z is in WM, then add ?xp?y-q?z-
Initially WM contains only one string (there is only one axiom):
---p-q----
With this rule we can produce many more strings, all of which get added to WM. This formal system is interestingly similar to a system you are familiar with. What is it?

From Formal System to Production System

In the pq system, once we have more than one string in WM, we can potentially apply the rule to more than one string. How do we choose which string to apply it to?

In a production system we have some algorithm which tells us which rule to apply at any given time. Choosing the rule and its operand (the string or symbol sequence it is applied to) is usually governed by system goals, which appear in WM. Here is an informal example of a production system which might help to account for the rather stupid behavior of the Sphex wasp:

```Rules:
1)if((goal (in_nest cricket) n))
then((goal (at_door cricket) n+1) and
(goal (safe nest) n+1) and
(do drag_in cricket n+1))

2)if((goal (at_door cricket) n)
then((do get cricket n+1))

3)if((goal (safe nest) n))
then((do checknest n+1))

WM:
(goal (in_nest cricket) 1)
```
Algorithm:
1. Find the highest ranked goal or action in WM. If there is a tie, simply take the first such goal or action.
2. Satisfy that goal or action
3. An action is satisfied by doing it.
4. When action (do x n) is satisfied, delete it from WM
5. A goal is satisfied by satisfying each bit of the RHS of the corresponding rule
6. When (goal x n) is satisfied, remove the goal and add x
Using this simple system, here are the contents of WM at successive times (assuming no malevolent researchers interfere):
```1)  (goal (in_nest cricket) 1)

2)  (goal (in_nest cricket) 1)
(goal (at_door cricket) 2)
(goal (safe nest) 2)
(drag_in cricket 2)

3)  (goal (in_nest cricket) 1)
(goal (at_door cricket) 2)
(get cricket 3)
(goal (safe nest) 2)
(drag_in cricket 2)

4)  (goal (in_nest cricket) 1)
(at_door cricket)
(goal (safe nest) 2)
(drag_in cricket 2)

5)  (goal (in_nest cricket) 1)
(at_door cricket)
(goal (safe nest) 2)
(checknest 3)
(drag_in cricket 2)

6)  (goal (in_nest cricket) 1)
(at_door cricket)
(safe nest)
(drag_in cricket 2)

7)  (in_nest cricket)
(at_door cricket)
(safe nest)

```
We have left out many details here. For example, we have left WM in a state in which it appears that the cricket is both at the door and in the nest... However, there are now no more applicable rules and the initial goal has been satisfied.

When a researcher interferes with this system by moving the cricket while the Sphex wasp is checking the nest, she is effectively resetting WM from stage 5 back to stage 3. The wasp blindly follows the algorithm and never progresses beyond stage 5.

Truth, Proof and Big Concepts

We have seen how a production system is a special case of a formal system. Strings which are in WM initially are axioms of the formal system. Strings which get added later are called theorems of the system, and are said to have been proved within the system, and hence to be true within the system. This may seem to have little to do with the way we usually use the words "proof" and "truth", but suppose for a minute that we all agreed that the axioms were true and that the rules were knock-down ways of argueing. Then it would necessarily follow that strings which got added later to WM were also true. In a formal system, there is no need, of course, for the axioms to be true or for the rules to be sensible. For example, in the pq system above, we could make the following identifications:
• p = '+'
• q = '='
• n hyphens stands for the number 'n'
In that case, the system can be easily seen to be producing true statements of the form 3+1=4, 3+2=5, 3+3=6 etc. However, nothing forces us to make this identification, and it is not the only such identification which will produce true statements. The next two interpretations are just as possible:
• p = '='
• q = 'subtracted from'
• n hyphens stands for the number 'n'
This interpretation allows us to interpret the theorems as 3 = 1 subtracted from 4, 3 = 2 subtracted from 5 etc. These are also true. If on the other hand, we chose to interpret the system thus:
• p = 'is the son of'
• q = 'and'
• n hyphens stands for the person mentioned in the n-th entry in the Bloomington phone book
then the system is seen to produce spurious allegations of kinship such as "Malik Aamir is the son of Erika Aalto and David Aarestad"

URL: http://www.indiana.edu/~gasser/prodsys.html
Last updated: 14 November 1995