How does one bring experimental data of human cognitive performance to bear on the general hypothesis that the architecture of the mind is appropriately described as a kind of production rule system? Recall that two systems are said to be weakly equivalent if they compute the same function; while strong equivalence adds the requirement that the two systems compute the function in the same way. But how can information be obtained that helps us determine how a person computes a function? It does not appear that we can directly report each step of our reasoning. However, at least for some cognitive tasks we can provide information about "what we are thinking" by verbally describing what is going through our mind while performing the task. This type of data is referred to as a verbal protocol.

    Newell and Simon pioneered and championed the use verbal protocols. They felt that the systematic collection of these types of observations could be used to test information processing models of human reasoning. Of course, we may not always be able to access information relevant to a cognitive task that we are performing. For example, the understanding of spoken speech happens rapidly and usually without "thinking about it." In contrast, we may sometimes spontaneously"think aloud" when solving puzzles. And verbal protocols has been used extensively in the development and design of expert systems.

     Cryptarithmetic problems were some of the first cognitive tasks studied using verbal protocols. The figure below presents an example of a Cryptarithmetic problem. You may want to at least begin solving this particular problem while "thinking aloud" in order to better follow the methods of protocol analysis.

     According to the information processing theories of Newell and Simon, human reasoning about problems such as these takes place via searching some problem space. And, that search is controlled using the architecture of a production rule system. One way to test these assumptions would be to determine whether the human subject's verbal protocol can be reproduced using a production rule system appropriately tailored to the subject's representation of the problem.

     However, recall that a problem may be solved in very different problem spaces. For example, in the section on search the Tower of Hanoi problem was represented as a state space as well as a problem reduction search. And, in fact there are additional spaces that could be defined in which a search for the solution to this problem could be carried out. The Cryptarithmetic Problem can be solved using different problem spaces. One such space is termed the set theoretic representation. In this representation, a state of the problem consists of two sets; the set of 10 alphabetic letters {A,B,D,E,G,L,N,O,R,T} and the set of 10 integers {0,1,2,3,4,5,6,7,8,9} together with some (partial) assignment of a letter to an integer. Limiting ourselves only to a complete assignment where each integer is assigned to one and only one letter yields 10! possible assignments. However, since we are given that 5 is assigned to D, there are only 9! or 362,880 possible assignments. This is a rather large number of states to search through for the solution to the problem! I know of no human subject who ever solved the task in this way. There is an algorithm that can be used to systematically and exhaustively generate this set. However, I would not want to implement this algorithm within a memory bounded production rule system.

     Thus, one expectation that is generated by thinking about the production rule architecture is that if the problem is solved, then it will be solved in a space that requires less memory and fewer computational resources to control the search. One such space is referred to as the algebraic representation of the problem. This representation consists of rewriting the problem as a set of six equations. For example, the first equation would be: D + D = T + 10 x c1 where c1 represents the carry of 0 or 1 involved in this addition. Note that in this representation the problem is decomposed into 6 subproblems - the six equations. And, in this space the subject's knowledge of algebra can be brought to bear on the problems. For example, consider the reasoning that allows the value of E to be determined. The figure below illustrates the reasoning required. Equation 5 is represented at the top of the figure. Knowledge of algebra allows the first step to be applied which eliminates O from the equation. Then four cases must be considered corresponding to whether c5 is 0 or 1 and whether c4 is 0 or 1. And as can be seen by examining the reasoning depicted in the figure, the only valid conclusion is that E be assigned the value of 9.

     This type of reasoning illustrates that reasoning in this algebraic representation of the problem can be carried out using far fewer memory resources than were required in the set theoretic space. And, one can imagine that the human reasoner will be able to verbally report much of this reasoning and may even annotate the reasoning using paper and pencil.

    Newell and Simon determined that this algebraic representation of the problem was the problem space utilized by their subjects. The next step was to precisely characterize this space. That is, a precise language for representing the states of the problem space and a specification of the operators is required. The figure below illustrates their specification of these two components. The definition of the language of states is given in BNF (Backus-Naur Form). This is basically a set of conventions for succinctly defining a context free language (that is what we have referred to as a Type 2 grammar). The nonterminal terms are enclosed in angle brackets. The symbol '::=' may be read as 'rewrites as" and the symbol ' | ' specifies a choice. For example, the states and operators are referred to by the nonterminal terms <knowledge-state> and <operator> respectively.