Definition, from Newell and Simon:
A physical symbol system consists of a set of entities, called symbols, which are physical patterns that can occur as components of another type of entity called an expression (or symbol structure). Thus, a symbol structure is composed of a number of instances (or tokens) of symbols related in some physical way (such as one token being next to another). At any instant of time the system will contain a collection of these symbol structures. Besides these structures, the system also contains a collection of processes that operate on expressions to produce other expressions: processes of creation, modification, reproduction and destruction. A physical symbol system is a machine that produces through time an evolving collection of symbol structures. Such a system exists in a world of objects wider than just these symbolic expressions themselves.
The hypothesis:
A physical symbol system has the necessary and sufficient means for general intelligent action.
Definition:
The system can interpret an expression if the expression designates a process and if, given the expression, the system can carry out the process.
Interpretation is really the pivot that lets you leverage computer science in thinking about intelligence. In particular, interpretation allows you to think of symbolic reasoning as leading to choices of action: a system can output the name of an action to perform and then interpret that name to do what it has decided. We've seen that that is crucial to a knowledge-level view of system behavior. In addition, interpretation is an important element in explaining why physical symbol systems can exhibit general intelligence. Interpretation is the main building block of universal computers, which can execute any specified algorithmic process; so having interpretation in a physical symbol system means that the system can take its information about the world - in terms of expressions that designate objects and properties - and put it to use in an arbitrarily open-ended way. I think this is something that got Newell and Simon particularly excited but it doesn't feature prominently in the paper or (especially) in the reaction to it in the literature.
The solutions to problems are represented as symbol structures. A physical symbol system exercises its intelligence in problem solving by search - that is, by generating and progressively modifying symbol structures until it produces a solution structure.
To state a problem is to designate (1) a test for a class of symbol structures (solutions of the problem) and (2) a generator of symbol structures (potential solutions). To solve a problem is to generate a structure, using (2), that satisfies the test of (1).
What makes a problem a problem is not that a large amount of search is required for its solution, but that a large amount would be required if a requisite level of intelligence were not applied. When the symbolic system that is endeavoring to solve a problem knows enough about what to do, it simply proceeds directly towards its goal…
Thus by this procedure [for solving equations], which now exhibits considerable intelligence, the generator produces successive symbol structures, each obtained by modifying the previous one; and the modifications are aimed at reducing the differences between the form of the input structure and the form of the test expression, while maintaining the other conditions for a solution.
For most real-life domains in which we are interested, the domain structure has not proved sufficiently simple to yield (so far) theorems about complexity, or to tell us, other than empirically, how large real-world problems are in relation to the abilities of our symbol system to solve them… It is likely that any system capable of matching [human] performance will have to have access, in its memories, to very large stores of semantic information… A particular, and especially a rare pattern can contain an enormous amount of information, provided that it is closely linked to the structure of the problem space. When that structure is "irregular", and not subject to simple mathematical description, then knowledge of a large number of relevant patterns may be the key to intelligent behavior.
First, each successive expression is not generated independently, but is produced by modifying one produced previously. Second, the modifications are not haphazard, but depend upon two kinds of information. They depend on information that is constant over this whole class of algebra problems, and that is built into the structure of the generator itself: all modifications of expressions must leave the equation's solution unchanged. They also depend on information that changes at each step: detection of the differences in form that remain between the current expression and the desired expression. In effect, the generator incorporates some of the tests the solution must satisfy, so that expressions that don't meet these tests will never be generated. Using the first kind of information guarantees that only a tiny subset of all possible expressions is actually generated, but without losing the solution expression from the subset. Using the second kind of information arrives at the desired solution by a succession of approximations, employing a simple form of means-ends analysis to give direction to the search.
Todd and Gigerenzer see themselves as the heirs to Herbert Simon and his tradition in psychology and cognitive science:
The research program on ecological rationality aims to explicate the mind-world interactions underlying good decision making.
Herbert Simon proposed the metaphor of the mind and world fitting together like the blades of a pair of scissors - the two must be well matched for effective behavior to be produced, and just looking at the cognitive blade will not explain how the scissors cut.
They describe their work as discovering heuristics - "simple decision algorithms that can work well in appropriate environments" that people use both in routine behavior and in important decisions. An example relevant to the famous "mate choice" in evolutionary psychology problem:
Heuristic: Try-a-dozen. To select a high-valued option from an unknown sequence, set an aspiration level at highest value seen in first 12 options, then choose next option that exceeds aspiration. This is ecologically rational if there is an unknown distribution of option values and no returning to previously seen options. Surprisingly, it leads to near-optimal performance over a wide range of sequence lengths (i.e., the number of available options matters little)
We return to this and other examples momentarily. The question is how to understand such heuristics as an instance of Newell and Simon's notion of heuristic search as discussed in their 1975 Turing Award Lecture.
Agre has a good perspective on these issues.
The ambivalence within Miller, Galanter and Pribram's theory of action [between a plan, which is selected whole from a library of action structures, and the plan, which explains all of an agent's activities as goal-directed behavior] reflects their failure to address adequately a central question: How is it that human activity can take account of the boundless variety of large and small contingencies that affect our everyday undertakings while still exhibiting an overall orderliness and coherence and remaining generally routine? In other words, how can flexible adaptation to specific situations be reconciled with the routine organization of activity?
I also like the rhetoric he uses to present his ideas as a contribution to cognitive science!
For these reasons, I propose that activity in worlds of realistic complexity is inherently a matter of improvisation. By "inherently" I mean that this is a necessary result, a property of the universe and not simply of a particular species of organism or a particular type of device. In particular, it is a computational result, one inherent in the physical realization of complex things.
Here is where things engage with the concept of choice as problem solving.
As thinking and acting intertwine, improvisation becomes a matter of continually redeciding what to do… This account is still Cartesian in the sense that each moment's action is brought about by an individual's discrete, deliberate choice, but this is still the only principled account of the relation between thought and action of which anyone can currently make any computational sense. At the same time, it is an interactionist view in one important respect: individuals continually choose among options presented by the world around them.
I propose to understand improvisation as a running argument in which an agent decides what to do by conducting a continually updated argument among various alternatives. This is an engineering proposal in the case of robots and a scientific proposal in the case of human beings… The argument [that agents conduct with themselves] might make reference to plans, maps, mnemonic devices, precedents from the actions of others, or anything else. Unanticipated issues can arise at any time, leading to new patterns of argument and possibly to changed courses of action. At any given moment, the complex of arguments leading to an agent's current actions is called its argument structure. As the agent interacts with its world, the argument structure will evolve.
Argumentation involves the adducing of arguments and counterarguments concerning a proposal for action.
Argumentation is problem solving and a way of thinking about responses to the current situation. The problem is not just to find an action to do. The problem is to find a good argument that justifies the choice of action to do next. An argument is good if all objections to it have been answered. You can test whether an argument is good in a particular situation by showing that all the potential counterarguments have been considered and disposed of. You can generate and search for such arguments by doing inference to construct arguments and taking stock of the relationships among them.
The point of the "try-a-dozen" heuristic is not to solve a problem of finding a possible action to do. When you encounter an option (for mate selection for example) it's obvious that taking it is a possible action to do. There's no problem there.
The problem is actually to find a good argument for taking it, or for not taking it. Todd and Gigerenzer's heuristics can be thought of as examples of such arguments. These arguments are surprising because they are simple to calculate, can only be objected to on a few relatively simple grounds, and because they tend to lead to good decisions.
The Take-the-Best heuristic. To decide which of two recognized options is greater on some criterion, search through cues in order of validity, stop search on the first discriminating cue, and choose the option favored by this cue. This heuristic is ecologically rational if cue validities vary highly, but there is moderate to high redundancy between cues. Surprisingly, it can decide more accurately than multiple regression, neural networks, and exemplar models when generalizing to new data.
In challenging environments with high variability, low predictability, and little opportunity for learning, good decisions may nonetheless be made more often by simple mechanisms than by complex ones… People are sensitive to the distribution of cues in an environment, appropriately applying either Take The Best of a weighted additive mechanism, depending on whcih will be more accurate… Exactly how people are able to determine which type of environment they are in, and then which heuristics will be appropriate to apply, remains an open question.