Definition
The General Problem Solver was a computer program written by Allen Newell, J. C. Shaw and Herbert Simon at the RAND Corporation, first running in 1957 and described formally in their 1959 paper Report on a General Problem-Solving Program. Its one genuinely new idea was structural rather than clever: GPS was the first program to keep its strategy for solving problems separate from its description of the problem, so the same engine could be pointed at symbolic logic, at trigonometry, or at a puzzle, simply by handing it a different table of operators.
That separation is why the program still matters and why the name is misleading. GPS was not general in the sense people now mean when they say a model is general. It solved formalised puzzles — theorems in propositional logic, the Tower of Hanoi, small algebraic rearrangements — and it never solved a real-world problem, because the search it performed grows exponentially with the length of the solution and no one has ever found a way around that for an unguided search. The interesting part of the story is not the ambition. It is that the failure has an exact size, in states, and that the two things that eventually fixed it are the two things a modern reasoning model does.
If you have arrived here looking for "AI that can solve any problem", that is Artificial General Intelligence (AGI), which is a claim about breadth with no agreed test. This page is about a named 1957 program, its mechanism, and its arithmetic. For the broader rule-and-logic paradigm GPS belonged to, see Symbolic AI.
How It Works
GPS ran on means-ends analysis. Given a current state and a goal state, it computed the most important difference between them, consulted a hand-written operator-difference table that said which operators are known to reduce which kinds of difference, and applied one. If that operator's preconditions were not met, the unmet precondition became a new goal and the whole procedure recursed on it.
Newell and Simon formalised this as exactly three goal types, and everything GPS ever did was some nesting of them: transform object A into object B; reduce difference D between A and B; apply operator Q to object A. Transform calls Reduce, Reduce calls Apply, Apply discovers a missing precondition and calls Transform. The recursion is the program.
The knowledge — the part that decides whether the search finishes this century — lives in two places, and neither of them was learned. It lives in the table that maps a difference to the operators relevant to it, and in the ordering GPS imposed on differences, which decided what "most important" meant. Both were written by hand, per domain. GPS was general; its competence was not.
Worked example: why Tower of Hanoi is easy
Take three discs on peg A that must end on peg C. The largest difference between now and the goal is that the biggest disc, disc 3, is on the wrong peg. Exactly one operator reduces it — move disc 3 from A to C — and its precondition is that discs 1 and 2 are out of the way, on peg B. That precondition is a smaller instance of the same problem, so means-ends analysis calls itself.
The arithmetic is why this works. With three pegs, each disc sits on one of three pegs and the stacking order on a peg is forced, so the entire state space of an n-disc puzzle is exactly 3ⁿ states, and the shortest solution is exactly 2ⁿ − 1 moves. For n = 3 that is a universe of 27 states and a 7-move plan. Even at most 3 legal moves from any position, an exhaustive search would finish in milliseconds on 1959 hardware. Means-ends analysis was not doing heavy lifting here; it was tidying up an already tiny space.
Hold that number, 27, next to the next one.
Why it stops: b to the power of d
The size of a search tree is b^d, where b is the branching factor (legal moves per state) and d is the depth of the solution. The AlphaGo paper puts the standard figures for two games at b ≈ 35, d ≈ 80 for chess and b ≈ 250, d ≈ 150 for Go — which gives roughly 10¹²³ and 10³⁶⁰ sequences respectively. Claude Shannon had reached the same conclusion for chess in 1950, estimating about 10¹²⁰ possible games and 10⁴³ legal positions.
Those totals are so large they stop meaning anything, so cut them down to something a program might plausibly attempt. Ten plies of chess — five moves each side, not a game, an opening — is 35¹⁰ ≈ 2.8 × 10¹⁵ positions. A 2026 machine evaluating a billion positions per second would need about 32 days. Each additional ply multiplies that by 35, so eleven plies is roughly three years, and twelve is a century.
Now compare. GPS's showcase success explored a world of 27 states. A single chess position offers 35 moves. The entire search space of the puzzle GPS solved is smaller than the branching factor of one position in a game it could not touch — and the gap between them is not a hardware problem. Between 1959 and today, machines got something like a billion times faster; 35^d eats a factor of a billion in six extra plies.
Newell and Simon believed the gap would close quickly. In their 1958 Operations Research paper Heuristic Problem Solving: The Next Advance in Operations Research they predicted that within ten years a digital computer would be world chess champion and would discover and prove an important new mathematical theorem. Deep Blue beat Garry Kasparov in 1997 — 39 years later, and by brute-force search with hand-tuned evaluation, not by means-ends analysis.
The predecessor: Logic Theorist
GPS was the generalisation of an earlier program. Logic Theorist, completed by the same three authors in 1956, proved 38 of the first 52 theorems in chapter two of Whitehead and Russell's Principia Mathematica — about 73% — and found a shorter proof of Theorem 2.85 than the one in the book. When they submitted that proof to the Journal of Symbolic Logic it was rejected on the grounds that a new proof of an elementary theorem was not notable, the reviewers apparently untroubled by one of the co-authors being a program.
Both programs were written in IPL (Information Processing Language), the list-processing language the team invented for Logic Theorist because nothing existing could represent a symbolic expression as data. IPL's ideas — lists, symbols manipulated at runtime — went straight into Lisp. GPS's real inheritance runs through that as much as through means-ends analysis.
Real-World Applications
GPS itself has no deployments and never had any. It is a 1959 research program, and a page that invented industry use cases for it would be lying. What it has instead is a lineage, and the lineage is deployed.
Automated planning is GPS with the difference table made explicit. Fikes and Nilsson's STRIPS, presented at IJCAI in 1971 and built to plan for the Shakey robot at SRI, used means-ends analysis directly, but formalised operators as preconditions plus add and delete lists. That representation became PDDL in 1998 and PDDL is still the language of the International Planning Competition. Planners in that family have flown: NASA's Remote Agent ran as flight software aboard Deep Space 1 in May 1999, the first autonomous planner to control a spacecraft, and the EUROPA planner behind it became MAPGEN, the system used on the ground to build the daily activity plans for the Mars Exploration Rovers. When a planner today decomposes "get the rover to the outcrop" into subgoals with unmet preconditions, it is running Newell and Simon's three goal types with better data structures.
Soar is the direct descendant inside cognitive architecture: Newell's own continuation of the GPS paradigm, still developed and still used to build agents that decompose goals into subgoals.
The two fixes arrived in 2016, from the other side of AI. AlphaGo did not beat b^d by searching harder. It attacked the two exponents separately: a value network truncated the tree by estimating the outcome of a position without playing it out, cutting d; a policy network sampled only plausible moves, cutting b. Those are precisely the two things GPS lacked, and the reason it lacked them is that in 1959 both had to be written by hand — the difference ordering was the value function and the operator table was the policy.
And the loop came back in language models. Chain-of-Thought (CoT) prompting and the search-at-inference behaviour described under Test-Time Compute are means-ends analysis with a learned policy instead of a hand-written table: state the goal, note the difference, take a step, recurse. The substrate changed from symbol structures to tokens, and the operator table changed from a hand-authored artefact to weights learned by Reinforcement Learning (RL). The control flow is recognisably the same. The hybrid version is explicit: the LLM+P framework (2023) has a language model translate a natural-language problem into PDDL, hands it to a classical planner descended from STRIPS, and translates the plan back — because the model is better at representing the problem and the planner is better at searching it.
Challenges
The three things that broke GPS are the three things that still break goal-decomposition agents, which is the reason a 1959 program is worth a modern reader's time.
The heuristic is the knowledge, and someone has to write it. GPS's generality was real but empty: the engine transferred between domains, the operator-difference table did not. Every new domain needed a human to enumerate the operators and rank the differences, which is the knowledge-acquisition bottleneck that Edward Feigenbaum named in 1977 and called, in 1983, the key bottleneck problem in artificial intelligence. Expert systems hit the same wall twenty years later for the same reason. It is only avoided when the table is learned rather than authored.
Formalising the problem is harder than solving it. John McCarthy's verdict on GPS was that "problems don't take this form in general" — the requirement that a problem arrive as expressions to be transformed, with a complete list of operators, excludes most of what people actually want solved. The related technical failure is the frame problem, stated by McCarthy and Hayes in 1969: to reason about what an action changes you must also state everything it leaves alone, and with m actions and n fluents the naive encoding needs m × n frame axioms. Writing down the world costs more than searching it.
Depth is unaffordable without a way to stop looking. A means-ends agent with no value function has no principled reason to abandon a branch, so it explores until it hits an arbitrary limit. This is the failure that shows up today in AI agent loops: an agent that proposes an action, evaluates the distance to the goal and recurses is doing means-ends analysis, and if nothing prunes the branching or truncates the depth, cost grows as b^d in tokens rather than in machine cycles. Two extra levels of subgoal on a task with ten plausible actions per step is a hundredfold bill. The historical lesson is specific: what rescued search was not more compute, it was a learned estimate of which branches are worth taking and how good a state is without finishing it. An agent design that omits both is repeating 1959 at 2026 prices.
Code Example
Means-ends analysis on the Tower of Hanoi, and the arithmetic that stopped it elsewhere.
def solve(n, src="A", dst="C", spare="B"):
"""Means-ends analysis, GPS style.
Goal: all n discs on `dst`.
Difference: the largest disc is on the wrong peg.
Operator: move it -- the only one that reduces that difference.
Precondition: the n-1 smaller discs are out of the way.
That unmet precondition becomes the next subgoal,
and the procedure recurses on it.
"""
if n == 0:
return []
return (
solve(n - 1, src, spare, dst) # subgoal: clear the way
+ [(n, src, dst)] # apply the operator
+ solve(n - 1, spare, dst, src) # subgoal: rebuild on target
)
plan = solve(3)
print(len(plan), "moves") # 7 == 2**3 - 1, provably minimal
print(3 ** 3, "states in the whole puzzle") # 27
# Same loop, no difference table worth having. Chess: b ~ 35 legal
# moves per position, d plies deep. This is what GPS ran into.
for d in (4, 6, 8, 10, 12):
nodes = 35 ** d
print(f"depth {d:>2}: {nodes:.2e} nodes, "
f"{nodes / 1e9 / 86400:.2f} days at 1e9 nodes/sec")
# depth 4: 1.50e+06 nodes, 0.00 days
# depth 6: 1.84e+09 nodes, 0.00 days
# depth 8: 2.25e+12 nodes, 0.03 days
# depth 10: 2.76e+15 nodes, 31.93 days
# depth 12: 3.38e+18 nodes, 39111.35 days
The recursion in solve is identical in shape to the one an agent framework runs today. The only difference that matters is that solve was handed a difference metric that happens to be perfect for this puzzle. Take that away and the second loop is what you get.