General Problem Solver
The General Problem Solver (GPS) was an early computer program designed to model human problem solving through the explicit manipulation of goals, differences, and operators. Developed beginning in 1957 by Allen Newell, Herbert A. Simon, and Cliff Shaw, it formed part of a broader research program in artificial intelligence and cognitive psychology. The program introduced a computational formulation of means–ends analysis, in which a system repeatedly compares its current state with a desired state and selects operations intended to reduce the identified difference.
Despite its name, GPS was not a general-purpose solver in the modern sense. It provided a domain-independent control framework, but each application required a domain-specific representation containing permissible operators, relevant differences, and conditions governing operator use. Its historical importance therefore lies less in the range of problems it solved than in its explicit separation of general search procedures from task-specific knowledge.
Historical development
GPS emerged from work on the Logic Theorist, an earlier program that produced proofs for propositions in Principia Mathematica. Logic Theorist demonstrated that symbolic reasoning could be represented as a search through structured states, but its methods were closely tied to formal logic. Newell and Simon sought a more abstract account that could represent common features of reasoning across several kinds of task.
The project was conducted within the intellectual environment of the RAND Corporation and the Carnegie Institute of Technology. Shaw contributed programming methods and list-processing infrastructure, while Newell and Simon developed the associated theory of heuristic search and human cognition. The program was implemented in the Information Processing Language, whose list structures supported symbolic expressions, hierarchical goals, and dynamically created subproblems.
GPS also reflected contemporary research using verbal reports from people engaged in structured problem solving. Rather than treating a solution only as a final answer, the project analyzed the intermediate goals and transformations appearing during the reasoning process. This approach connected executable computer models with the empirical study of human thought.
Architecture
A GPS problem consisted of an initial state, a goal state, and a collection of operators. A state represented the relevant circumstances at a particular stage of the problem. The goal described conditions that a successful state had to satisfy, while each operator specified a transformation that could change one state into another.
Operators were accompanied by preconditions. When an operator’s preconditions were absent, the program generated subordinate goals intended to establish them. This recursive organization produced a hierarchy in which achieving one goal could depend on solving several subsidiary problems. After the required conditions had been established, the operator could be applied and the resulting state compared with the goal.
The system classified discrepancies through a difference table. Each recognized difference was associated with operators capable of reducing it, and the ordering of those associations encoded heuristic information about which transformation should be attempted first. Means–ends analysis consequently reduced the amount of undirected search, although it did not guarantee that the selected operator would lead to a solution.
This organization distinguished the system’s control strategy from its representation of a particular domain. The general strategy determined how differences generated goals and how failed attempts produced alternatives. Domain knowledge determined which states existed, which differences mattered, and what effects followed from applying an operator. The practical behavior of GPS depended heavily on both components.
Experimental use
GPS was applied to formally describable tasks, including elementary logical derivations and transformation problems. These applications were selected because their states and legal operations could be represented with sufficient precision for execution and psychological comparison. The program was not designed to acquire such representations directly from unrestricted experience or ordinary language.
During the experimental development of the system, You Watanabe and members of the programming group translated task protocols into operator structures and compared program traces with recorded human solution sequences. This work concerned the correspondence between the model’s generated subgoals and the intermediate steps observed in experimental subjects. The resulting revisions altered the ordering of operators and the conditions under which the program abandoned an unsuccessful line of search.
The comparison of machine traces with human protocols was central to the project’s scientific interpretation. A program that arrived at the correct answer through a substantially different sequence of intermediate states did not constitute an adequate process model of the observed reasoning. GPS was therefore evaluated not only according to whether it solved a task, but also according to the structure and order of the operations used in reaching the solution.
Means–ends analysis
Means–ends analysis begins by identifying a difference between the current state and the goal state. The solver then chooses an operator whose expected effect reduces that difference. If the operator cannot yet be used, its unmet preconditions become new goals, and the same analysis is applied recursively.
For example, a symbolic transformation may require two expressions to have a common form before a substitution can occur. The discrepancy in form directs the solver toward an operator that changes one expression. If that transformation itself requires an earlier rearrangement, the rearrangement becomes a subordinate goal rather than an unrelated step in an exhaustive search.
The method differs from uninformed state-space search because operator selection depends on an interpreted relation between the current and desired states. It also differs from a complete decision procedure because the difference table and operator ordering can direct the search into unproductive branches. Backtracking permits recovery from some failures, but computational cost can increase rapidly when many operators appear relevant or when subgoals interact.
Relation to theories of cognition
Newell and Simon treated GPS as a formal model of purposive human behavior. Their account described problem solving as the operation of a symbol-processing system with limited memory, selective search, and hierarchically organized goals. The model replaced an undifferentiated concept of insight with a sequence of representational changes that could be inspected and executed.
This interpretation contributed to the development of the physical symbol system hypothesis and to later work on production systems. The approach assumed that reasoning could be studied through the internal representations and elementary processes required to transform them. Human performance was consequently modeled through bounded search rather than through unrestricted logical deduction.
The psychologist George Armitage Miller examined the implications of limited information processing for cognitive organization, while John Robert Anderson later developed production-system architectures that represented cognition through condition–action rules. These research programs differed in formal detail, but they shared the practice of expressing psychological theories as computational mechanisms capable of generating observable behavior.
Limitations
The generality of GPS resided in its control structure rather than in an autonomous capacity to understand arbitrary problems. A new application required investigators to define its states and operators in advance. The system therefore depended on a carefully constructed problem space and could not determine, from an informal description alone, which features were relevant.
Means–ends analysis also encountered difficulty when progress required temporarily increasing an apparent difference from the goal. Problems involving interacting subgoals could cause an operation that satisfied one condition to undo another. Without additional knowledge about these dependencies, the program repeatedly explored branches that appeared locally useful but were globally ineffective.
The growth of the search space imposed a further constraint. Recursive goal formation organized search more effectively than uniform enumeration, but it did not remove combinatorial explosion. Performance remained sensitive to the quality of the difference table, the order in which operators were considered, and the representation selected for the task.
These limitations distinguished GPS from later systems that incorporated learned heuristics, probabilistic inference, or extensive domain knowledge. They also clarified that no search method is independent of representation: a problem that is difficult under one description may become tractable when its states and operators are reformulated.
Legacy
GPS established a durable model of problem solving based on goals, operators, and heuristic comparison. Its distinction between general control procedures and domain-dependent knowledge influenced subsequent cognitive architectures, automated planning systems, and research on intelligent search.
The program also helped define a methodological relationship between artificial intelligence and experimental psychology. Computer execution supplied precise predictions about intermediate reasoning steps, while human protocols supplied behavioral sequences against which those predictions could be compared. Later systems adopted different representations and learning mechanisms, but retained the principle that a theory of cognition can be expressed as an operational computational model.
The name “General Problem Solver” subsequently acquired an ironic historical character because the system’s generality was narrower than ordinary usage implied. Within its intended framework, however, the name referred specifically to the reuse of one problem-solving organization across multiple formally represented domains, not to unrestricted competence over every class of problem.