Logic Theorist: Why Some Call It the First AI Program

The Logic Theorist was a computer program finished in 1956 by Allen Newell, Herbert A. Simon and Cliff Shaw. Wikipedia's article on it says it was the first program deliberately built to reason automatically, and that it has been called "the first artificial intelligence program". This post explains what the program did, how it worked, why that label is both fair and contested, and what people made of it.

If you would like to explore where machines that reason could lead as a story, Contain ASI is a story strategy game for 1 to 4 players in your browser, where you try to keep four fictional AI labs from crossing into recursive self-improvement before 2027.

The Logic Theorist in short

The program proved mathematical theorems. It took on chapter 2 of Principia Mathematica, the work by Alfred North Whitehead and Bertrand Russell, and proved 38 of its first 52 theorems. For Theorem 2.85 it found a new, shorter proof. Simon showed that proof to Russell himself, who, the article says, "responded with delight".

The authors tried to publish the new proof in The Journal of Symbolic Logic. It was rejected as not notable, which the article says apparently overlooked that one of the authors was a computer program.

Is it really the first AI program? The article's footnote is careful: it is usually considered the first true AI program, but Arthur Samuel's checkers program was released earlier, and Christopher Strachey also wrote a checkers program in 1951. So "first" depends on what you count.

Where the idea came from

When Newell and Simon began in 1955, the field of artificial intelligence did not exist yet. The term would not be coined until the following summer. We tell that summer in our post on the Dartmouth workshop.

Simon was a political scientist who studied how bureaucracies work and developed the theory of bounded rationality, for which he later won the 1978 Nobel Memorial Prize in Economic Sciences. While consulting at RAND in the early 1950s, he saw a printer typing out a map using ordinary letters and punctuation as symbols. That made him think a machine that handles symbols could simulate decision making, and maybe even human thought.

Newell, a RAND scientist, had written the program that printed the map. His turning point came in 1954, when Oliver Selfridge described his work on pattern matching. Newell saw how simple programmable units could combine into complex behavior. "It all happened in one afternoon," he later said.

From cards to a computer

Their first project was a program to prove theorems of the kind found in Principia Mathematica. They asked Cliff Shaw, a RAND programmer, to help.

The first version never ran on a machine. In January 1956 the team wrote the program on 3x5 cards and handed one to each person in a group, including Simon's wife, his three children and some graduate students. Each person acted as one part of the program. Simon later called it "nature imitating art imitating nature". Shaw then ran the program on the computer at RAND's Santa Monica facility.

How the program worked

The Logic Theorist handled logical expressions. The article explains that an expression is stored as a tree: each node is an element with up to 11 attributes, and the root of a statement like "not P implies (Q and not P)" points to its two sub-expressions. Working memories held one element each, and usually 1 to 3 were in use. Storage memories held whole expressions, including all the axioms and every theorem proven so far.

On top of that sat four levels of process. Instructions were like assembly code. Elementary processes were like subroutines. Methods were built from those, and one executive control method ran the show. That executive method tried each of the four methods, in sequence, on every theorem it needed to prove.

In plain words: each method finds a stored theorem that fits part of the goal and, when it cannot finish, hands back a smaller problem to solve. Chaining forward works from the start of a chain "A implies C", and chaining backward from its end.

A worked example: follow a toy proof search

This is a made-up miniature in the spirit of the four methods, not one of the program's real proofs, which used the symbols of Principia Mathematica. Try it on paper.

1. Set the store. The program already holds two proven facts: "A implies B" and "B implies C", where A, B and C are three fixed statements.
2. Set the goal. Prove "A implies C".
3. Try substitution. Is there a stored fact that can be turned into "A implies C"? No: neither stored fact matches it.
4. Try detachment. It needs a stored fact that has the whole goal as its right side. There is none.
5. Try chaining forward. Find a stored fact starting with A. "A implies B" fits. The new subproblem is "B implies C".
6. Solve the subproblem. Substitution finds "B implies C" in the store. The goal is proven: A leads to B, and B leads to C.

Now try your own chain: "If I sleep, I focus. If I focus, I finish the draft." What is the goal, and what is the subproblem? You have just seen reasoning as search, the next idea.

What the Logic Theorist added to AI

The article lists three ideas the program introduced that stayed central to AI research.

• Reasoning as search. The program explored a tree. The root was the starting hypothesis, each branch was one deduction, and somewhere in the tree sat the proposition to prove. A path of deductions from the root to that proposition was a proof.
• Heuristics. Newell and Simon saw the tree would grow exponentially, so they trimmed branches with rules of thumb. They borrowed the word "heuristics" from George Pólya's How to Solve It. The article says heuristics remain an important way to tame exponentially growing searches.
• List processing. To run the program, the three built a language called IPL. Its symbolic list processing later formed the basis of McCarthy's Lisp, a language AI researchers still use. You can read about him in our post on John McCarthy.

Newell and Simon went on to found one of the first AI laboratories, at the Carnegie Institute of Technology, and to develop the General Problem Solver, Soar and a unified theory of cognition. It belongs to what we call symbolic AI; see also the history of AI.

Big claims and a lukewarm welcome

In the summer of 1956, John McCarthy, Marvin Minsky, Claude Shannon and Nathan Rochester organized a conference on what they called "artificial intelligence", a term McCarthy coined for the occasion. Newell and Simon presented the Logic Theorist there. The article says it was met with a lukewarm reception. Pamela McCorduck writes that nobody save Newell and Simon themselves sensed the long-range significance of what they were doing.

The claims they made were large. In January 1956, Simon told a graduate class, "Over Christmas, Al Newell and I invented a thinking machine". He later wrote that they had solved "the venerable mind-body problem", explaining how a system made of matter can have the properties of mind.

The article adds that the idea that machines can have minds just as people do was later named "Strong AI" by the philosopher John Searle, and that it remains a serious subject of debate. You can follow one famous objection in our post on the Chinese room argument. McCorduck's own view is that the program was "proof positive that a machine could perform tasks heretofore considered intelligent, creative and uniquely human". She also sees in it the debut of the information processing model of the mind, which Newell and Simon later formalized as the physical symbol systems hypothesis.

The Logic Theorist and Contain ASI

The Logic Theorist was a first step: a machine doing something once thought uniquely human. Contain ASI is fiction about a much later, imagined step. Its page reads "January 2024. Four AI labs. One race." and gives you three years to keep every lab from crossing into recursive self-improvement before 2027. The page says it is inspired by the AI 2027 scenario, and that all its labs, people and events are fictional. It is a story, not a forecast.

Frequently asked questions

What was the Logic Theorist?

A computer program completed in 1956 by Allen Newell, Herbert A. Simon and Cliff Shaw. It was built to prove mathematical theorems and has been called the first artificial intelligence program.

Was the Logic Theorist really the first AI program?

It is usually considered the first true AI program, and the first built for automated reasoning, though Arthur Samuel's checkers program was released earlier.

What did the Logic Theorist prove?

It proved 38 of the first 52 theorems in chapter 2 of Principia Mathematica, and found a shorter proof of Theorem 2.85.

How did the Logic Theorist work?

It stored logical expressions as trees and kept every proven theorem in memory. For each goal it tried four methods in sequence (substitution, detachment, chaining forward and chaining backward), turning failures into smaller subproblems.

Why does the Logic Theorist matter to AI?

It introduced reasoning as search, heuristics and symbolic list processing, three ideas the article says became central to AI research. It also sparked the debate over whether a machine can have a mind.

Get started

The Logic Theorist showed that a machine could chase a proof through a tree of options. If you would like to explore, as fiction, what a later race between machines might look like, play Contain ASI: a story strategy game for 1 to 4 players that runs in your browser. Its labs, people and events are all fictional.