In the summer of 1956, a program running at the RAND Corporation in Santa Monica printed a proof of a theorem in formal logic. Nobody had typed the proof in. The program had searched for it.
That program was the Logic Theorist. It is the first piece of software built to reason, and it ran before the words "artificial intelligence" had been spoken in public.
Principia Mathematica (1910) builds all of logic from five axioms and one definition. Its second chapter derives the first 52 theorems from them.
The Logic Theorist was given the axioms, the theorems in the book's order, and nothing else. Its job was to find a proof for each one.
| Ref. | Axiom |
|---|---|
| ∗1.2 | (p ∨ p) ⊃ p |
| ∗1.3 | q ⊃ (p ∨ q) |
| ∗1.4 | (p ∨ q) ⊃ (q ∨ p) |
| ∗1.5 | (p ∨ (q ∨ r)) ⊃ (q ∨ (p ∨ r)) |
| ∗1.6 | (q ⊃ r) ⊃ ((p ∨ q) ⊃ (p ∨ r)) |
A proof is a path. The theorem sits at the top. Every rule that could apply opens a branch below it, and the program walks down looking for a branch that ends on an axiom.
Most branches lead nowhere. The program cuts them early using rules of thumb its authors called heuristics. That word, and that idea, entered computing here.
One proof search. Three branches opened at each level; one followed to the bottom.
This is the first theorem the program proved on the machine, on 9 August 1956. Nothing below was written in advance. The program chose the axiom, chose the substitution, and noticed that a definition applied in reverse.
Step through it.
Computers had done arithmetic for a decade. Checking a given proof line by line is bookkeeping. The claim rests on how the proof was found, and three ideas carry it.
Thinking modelled as walking a tree of possibilities. Still the standard model in AI and in cognitive psychology.
Rules of thumb that decide which branches are worth opening. Why it ran in a few thousand words of memory, and why it missed 14 theorems.
Formulas held as linked lists that grow and nest at run time. Invented for this program; adopted by Lisp two years later.
The program was not told the answers and did not try everything. It formed subgoals, judged them, and gave up on bad ones. A machine chose how to find the answer. That was new.
Designed the search strategy. Decided in 1954 that a computer could do symbolic work, not only arithmetic.
Supplied the model of how people solve problems. Later a Nobel laureate in economics.
Wrote the language it ran in and the code that ran on JOHNNIAC. The least credited of the three.
Before the code could run, in January 1956, Simon handed index cards to his wife, his three children and a few students. Each person played one subroutine. Executed by hand, the program produced a proof.
For theorem ∗2.85 the program found a proof shorter and cleaner than the one Russell had printed. Its authors submitted it to the Journal of Symbolic Logic, listing the program as a co-author.
The journal declined. A new proof of an elementary theorem, it said, was not notable.
Russell, shown the machine's proof, responded with delight.
It is the first recorded case of a program producing a result its authors did not know, and the first rejection of a paper written by one.
Shown at Dartmouth in 1956, the program got a lukewarm reception. Within a few years its ideas were the field.
Every system that searches a tree of next steps and prunes it by a rule descends, in structure, from this program.
$LOGIC takes the Logic Theorist as its narrative. The story you just read is stated as it happened. It launches on ARC mainnet. The parameters are below; fields marked pending are filled at launch.
That is the whole story: a program that searched for a proof, found one, and started a field. Everything above is on the record, sourced from Newell, Shaw and Simon's own papers.