📄 Report on a general problem-solving program

Summary

This draft report by Newell, Shaw and Simon, a working manuscript dated December 1958, explains how computer programs can serve as theories of problem solving, both in the abstract and in human thinkers. The work began with the Logic Theorist, which searched for proofs in the sentential calculus of Whitehead and Russell using heuristics instead of a guaranteed algorithm. The authors then recorded college students thinking aloud while they rewrote symbolic-logic expressions under fixed transformation rules. They used these protocols to revise the program into the General Problem Solver (GPS).

GPS keeps domain content separate from very general methods such as functional analysis and planning, and it matched much of the subjects' recorded behaviour. The report frames problems as objects transformed by operations, or as a generator of candidates paired with a test. It argues that blind search fails because the search space grows exponentially, so heuristics are essential. The paper is an early statement of heuristic search as the core of artificial intelligence and cognitive modelling.

Key points

• The Logic Theorist proves theorems from Principia Mathematica's sentential calculus by heuristic, symbolic manipulation rather than truth tables.
• GPS came from think-aloud protocols of sophomores transforming logic expressions, such as turning (p v q).(-p.q) into a target form.
• The planned demonstration domains are symbolic logic, trigonometric identities, integration via tables, and chess.
• Exhaustive search generates roughly (1/2)·b^d objects, where b is the number of branches and d is the depth. For chess, with b ≈ 30 and d ≈ 40, this gives about 10^120.
• The generator-test formulation is described as nearly universal. As an illustration, all novels fit within a space of about 30^(10^6) character strings. Heuristics are needed to prune such spaces.