GPS: General Problem Solver
Newell and Simon develop GPS, the first program attempting to simulate human problem-solving processes.
Overview
In 1959, Allen Newell and Herbert Simon developed the General Problem Solver (GPS) at Carnegie Mellon. GPS employed "means-ends analysis" method, identifying differences between current and goal states, then selecting operations to reduce those differences. GPS could solve logic theorem proving, geometry problems, and various other tasks, representing early AI's pursuit of "general intelligence." Although GPS had limited capabilities, its problem decomposition and heuristic search ideas were profoundly influential.
Study Notes
Background, mechanics, impact, and key takeaways in one read
Background & Context
In 1959, Newell, Shaw, and Simon presented the General Problem Solver (GPS) at the International Conference on Information Processing in Paris. Growing out of the Logic Theorist, its ambition was grander: a domain-independent "general" solver. Automated reasoning then leaned on exhaustive search, and problem knowledge was tangled with the solving strategy in one codebase—switch domains and you rewrote everything. The trio asked whether a general problem-solving mechanism could be cleanly separated from domain knowledge. Implemented at RAND and Carnegie Tech on machines like the JOHNNIAC, GPS was claimed to be both software and a computational theory of how humans solve problems.
Key Points
- 1Proposed at the 1959 Paris conference, GPS generalized the Logic Theorist into a broader, domain-independent solver.
- 2Its key innovation separated a general solving mechanism from domain knowledge; swap domains by swapping tables.
- 3It used means-ends analysis: compare current and goal states, pick an operator that reduces the biggest difference.
- 4A hand-written "difference table" mapped which differences each operator could reduce; the knowledge was given, not learned.
- 5If an operator's preconditions failed, GPS set them as subgoals and launched a fresh copy of itself—classic recursion.
- 6It solved toy problems like propositional logic, trigonometric identities, and Tower of Hanoi, never real-world tasks.
How It Works
GPS's engine is means-ends analysis. Given a current and a goal state, it computes the most important difference between them, consults a hand-written "difference table" to find an operator that reduces it, and tries to apply that operator. If the operator's preconditions are unmet, that gap becomes a new subgoal and GPS launches a fresh instance of itself to solve it—recursing until no difference remains. Picture wanting Sammy at school: the difference is "not at school," the operator is "drive," whose precondition is "car has power"; a dead battery becomes a subgoal, satisfied by "call a mechanic." A goal stack manages these nested subgoals. All the intelligence lives in two hand-written tables—difference-to-operator mapping and difference ordering—and the knowledge is given, not learned.
Impact & Legacy
GPS was the first to decouple a general solving mechanism from domain knowledge, an architectural idea that prefigured expert systems and knowledge engineering. Its means-ends analysis also became the standard computational model of human problem-solving in cognitive science (Newell and Simon's 1972 "Human Problem Solving"). Its limits are clear: unguided search grows exponentially with solution length, so it solved only toy problems and never real tasks; "general" meant the mechanism, not the competence. Yet its "state–difference–operator–recursive subgoal" frame remains the prototype of modern planners.
Key Takeaways
- Separating mechanism from knowledge is the key architectural principle for reusable, extensible systems.
- Working backward from goals and resolving preconditions via subgoals is a strategy shared by humans and machines.
- "General" must be qualified: GPS was general in mechanism, not in competence.
Glossary
A problem-solving method that compares current and goal differences, picks an operator to reduce them, and recurses on subgoals.
A hand-written map from differences to the operators that can reduce them; the main carrier of GPS's knowledge.
Newell and Simon's claim that symbol manipulation is necessary and sufficient for general intelligence; GPS was its validation.
Related Links
Related Events
Logic Theorist: First AI Program
Allen Newell and Herbert Simon create Logic Theorist, the first AI program capable of proving mathematical theorems.
Soar Cognitive Architecture
John Laird, Allen Newell, and Paul Rosenbloom develop Soar, an important attempt at a general cognitive architecture.