General Problem Solver
Era 2 · AI is born (1943–1979) › Symbolic AI
- Lineage
- Symbols and logic
- Kind
- Implementation
Who
RAND Corporation, Carnegie Institute of Technology
What happened
Newell, Shaw, and Simon write the General Problem Solver (GPS), a program meant to solve any problem that can be formalized. They describe it in 1959 in "Report on a general problem-solving program."
Why it mattered
It separates the knowledge specific to each problem from the general method for solving it, means-ends analysis: compare the situation with the goal, choose an operation that reduces the difference, and set subgoals.
The full story
Logic Theorist knew only logic. The next step for Newell, Shaw, and Simon was to find a method that would work for any problem, and they based it on how people solve problems.
The method, called means-ends analysis, works like this: the program compares the current state with the goal, identifies the most important difference, looks for an operation that reduces it, and, if that operation cannot be applied yet, sets itself the subgoal of reaching a state where it can. The specific knowledge, which operations exist and which differences they reduce, is supplied separately, in tables, and the same program solves different problems when those tables change.
GPS solved well-defined problems, such as the Towers of Hanoi and proofs in logic and geometry. But on real problems the number of paths grew so large that the search choked: the combinatorial explosion that symbolic AI would run into again and again.
Its legacy was twofold. In AI, the idea of separating knowledge from the reasoning method led to expert systems. In psychology, using programs as theories of how people think founded part of cognitive science, and carried on in architectures such as Soar.
Builds on
Logic Theorist (1955)
Documented direct influence
The same authors generalize Logic Theorist's heuristic search to any problem that can be formalized
Leads to
STRIPS (December 1971)
Documented direct influence
STRIPS searches for its plan with GPS's means-ends analysis
Threads that pass through here
- From general reasoning to expert knowledge (step 2 of 6)
Sources
Original source
- The logic theory machine: A complex information processing system. IRE Transactions on Information Theory, 2(3), pp. 61-79 (opens in a new tab). Allen Newell and Herbert A. Simon, 1956
Further reading
How to cite
“General Problem Solver.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/general-problem-solver
This entry was last reviewed on November 13, 2026.