General Problem Solver introduced by Newell, Shaw and Simon
In 1959, Allen Newell and Herbert A. Simon at the RAND Corporation and Carnegie Institute of Technology, with J. C. Shaw, presented the General Problem Solver, a computer program that separated problem-solving strategy from domain knowledge using means–ends analysis.
Background
By the mid-1950s, the researchers trying to get computers to reason were already making real progress. Allen Newell and Herbert A. Simon, working between the RAND Corporation and the Carnegie Institute of Technology, had built the Logic Theorist with their colleague J. C. Shaw. That program could prove theorems in symbolic logic by searching through possible steps until it found one that worked. It was a genuine achievement, but it was also deeply specific: its knowledge about logic and its method for solving problems were tangled together inside the same code.
That entanglement was a problem. A program built to prove theorems could not be turned towards a different task without essentially rewriting it from scratch. Researchers were left asking whether anything general could be said about how to solve problems, or whether every domain would always demand its own bespoke machinery.
Meanwhile, the theoretical tools available were limited. Most automated reasoning depended on exhaustive search, trying possibilities in sequence until something worked. The search spaces for even modestly complex problems were enormous, and computers of the era were slow. Getting a machine to reason in any directed, purposeful way, rather than just grinding through combinations, was an unsolved question.
What happened
In 1959, Newell, Shaw, and Simon presented a program they called the General Problem Solver, GPS, at the International Conference on Information Processing in Paris. The paper, “Report on a General Problem-Solving Program”, described an architecture built around a clean separation: on one side sat a general reasoning method, and on the other sat descriptions of whatever problem you wanted to solve. The same reasoning engine could, in principle, be pointed at different tasks by swapping in different problem descriptions.
The reasoning method at the heart of GPS was means–ends analysis. The program would compare where it currently was to where it wanted to be, identify the most important difference between the two states, and then look for an operation that could reduce that difference. If applying that operation required some precondition that was not yet met, GPS would set a new sub-goal to meet it first, and recurse. The process kept going until no meaningful difference remained between the current state and the goal.
That might sound simple, but it gave the program something most of its predecessors lacked: a way to work backwards from what it wanted, rather than forward from what it had. Newell, Shaw, and Simon also used GPS as a psychological claim. In their 1961 paper “GPS, a Program that Simulates Human Thought”, they argued that the same means–ends structure described how people actually reason through problems, grounding the program in experimental work on human problem-solving. GPS was, for them, both a working piece of software and a theory of cognition.
The program was demonstrated on tasks including symbolic logic and the rearrangement of formal expressions. It did not scale to large or open-ended problems, and it was not deployed in any practical system at the time. Its contribution was architectural: showing that a single mechanism, given the right description of a problem, could reason about it in a directed way.
Why it mattered
GPS was the first program explicitly designed to separate a general problem-solving mechanism from domain-specific knowledge, a structural idea that prefigured the architecture of later expert systems and knowledge-based AI. Its formalisation of means–ends analysis, repeatedly comparing a current state to a goal state and selecting operators to reduce the difference, gave AI researchers a concrete computational account of goal-directed reasoning. The program also shaped cognitive science: Newell and Simon used GPS as a model of human problem-solving, influencing decades of psychological research on cognition.
People
Allen Newell, Herbert A Simon, J C Shaw
Organisations
RAND Corporation, Carnegie Institute of Technology
Sources
- Report on a General Problem-Solving Program.ACM Digital Library (Proceedings of the International Conference on Information Processing, UNESCO, Paris).Primary source
- GPS, a Program that Simulates Human Thought.American Psychological Association / Lernende Automaten (H. Billing, ed.), Oldenbourg, Munich, later reprinted in Feigenbaum & Feldman, Computers and Thought.Primary source
- Means–Ends Analysis as a General Problem-Solving Technique (review context in historical AI surveys).Springer.Secondary
Cite this page
AI Achievements. (1959). General Problem Solver introduced by Newell, Shaw and Simon. Retrieved 2026-08-22, from https://achievements.ai/milestone/general-problem-solver-gps-by-herbert
@misc{achievements_general_problem_solver_gps_by_herbert,
title = {General Problem Solver introduced by Newell, Shaw and Simon},
author = {{AI Achievements}},
year = {1959},
url = {https://achievements.ai/milestone/general-problem-solver-gps-by-herbert}
}