Logic Theorist

• 1. Introduction

  ›

  Logic Theorist, completed in 1956 by Allen Newell, Herbert A. Simon, and Cliff Shaw, is widely described as the first artificial intelligence program ever built. It arrived before the field of artificial intelligence even had a name. When Newell and Simon began the work in 1955, the term "artificial intelligence" had not yet been coined. So what exactly had they built, and how did a political scientist, a RAND logistics researcher, and a computer programmer come to create something that proved 38 of the first 52 theorems in Bertrand Russell and Alfred North Whitehead's Principia Mathematica? The answers trace back to a printed map, a single electrifying afternoon, and a hand-simulation carried out at a kitchen table using index cards.

• 2. Two Men, One Idea

  ›

  Herbert Simon was not a computer scientist. He was a political scientist whose career had been devoted to studying how bureaucracies function and to developing his theory of bounded rationality, a body of work that would eventually earn him the Nobel Memorial Prize in Economic Sciences in 1978. What drew him toward thinking machines was something he saw while consulting at RAND Corporation in the early 1950s: a printer typing out a map, using ordinary letters and punctuation as symbols. That image locked something into place for him. A machine that could manipulate symbols, he reasoned, might be able to simulate decision making. It might even simulate the process of human thought itself.

  Allen Newell had written that map-printing program. He was a RAND scientist working on logistics and organization theory. His decisive moment came in 1954 when a researcher named Oliver Selfridge visited RAND to describe his work on pattern matching. Watching that presentation, Newell experienced something he described as a rare scientific epiphany. He later recalled being "completely absorbed for ten to twelve hours," working without the usual layered self-awareness of normal thought, convinced he had glimpsed "a new path." "I haven't had that sensation very many times," he said. "I'm pretty skeptical, and so I don't normally go off on a toot, but I did on that one."

  The two men began to discuss whether machines could be taught to think. Their first agreed-upon target was a program that could prove the kinds of mathematical theorems found in Russell and Whitehead's Principia Mathematica. To build the actual code, they recruited Cliff Shaw, also from RAND. Newell later acknowledged him plainly: "Cliff was the genuine computer scientist of the three."

• 3. The Kitchen Table Test

  ›

  Before any computer ran Logic Theorist, Simon tested it by hand. In January 1956, he gathered his wife, three children, and several graduate students in his home. He wrote the program's logic onto 3x5 cards and distributed them among the group. Each person became, in effect, a single component of the computer program. Simon later recalled the strangeness of that moment with a phrase that stayed with him: "Here was nature imitating art imitating nature."

  The hand-simulation worked. The group successfully proved theorems, demonstrating that the program's logic was sound before a single line of it ran on a real machine. Eventually Shaw was able to run Logic Theorist on the computer at RAND's Santa Monica facility, and the results held. The program proved theorem after theorem from the Principia Mathematica's second chapter. One proof, for theorem 2.85, turned out to be more elegant than the one Russell and Whitehead had produced themselves. Simon managed to show the new proof to Russell, who responded with delight. When the team attempted to publish it in The Journal of Symbolic Logic, the editors rejected it on the grounds that a new proof of an elementary theorem was not notable. The rejection apparently overlooked the fact that one of the authors was a computer program.

• 4. A Cold Reception

  ›

  In the summer of 1956, John McCarthy, Marvin Minsky, Claude Shannon, and Nathan Rochester organized a conference on what McCarthy called "artificial intelligence," a term he coined specifically for the occasion. Newell and Simon arrived eager to show Logic Theorist to the assembled researchers. What they received was a lukewarm reception. Writer Pamela McCorduck, drawing on accounts from those present, concluded that "nobody save Newell and Simon themselves sensed the long-range significance of what they were doing."

  Simon later confessed that the team had probably been "fairly arrogant" in how they presented the work. But he also felt a certain irony in the dismissal. They had already produced the first working example of exactly what the conference had gathered to discuss, and the room had not paid much attention. "They didn't want to hear from us, and we sure didn't want to hear from them," Simon recalled. "We had something to show them!" The gap between what the program had already accomplished and how it was received at that founding moment of AI would take years to close.

• 5. How the Program Worked

  ›

  Logic Theorist operated on logical expressions structured as abstract syntax trees, each node carrying up to 11 attributes. The program used two kinds of memory: working memory, which held a single element and typically ran one to three instances at once, and storage memory, which held the full set of axioms and already-proven theorems in list form.

  Four methods drove the reasoning process. Substitution tried to transform a given expression into a known theorem by substituting variables and logical connectives. Detachment worked by locating a proven theorem whose conclusion could be matched to the target expression, then attempting to prove the premise by substitution. Forward and backward chaining extended this by searching for intermediate theorems that could bridge from what was known to what needed to be proved. An executive control method then applied all four in sequence across each theorem the program was trying to establish.

  At the lowest level, the program's instructions resembled assembly code: primitive operations on expressions in working memory, or conditional jumps to the next instruction. Elementary processes grouped these instructions into reusable subroutines. The layered architecture, moving from raw instructions up through methods to executive control, was itself a significant structural innovation for its time.

• 6. Ideas That Outlasted the Program

  ›

  Reasoning as search was one of Logic Theorist's core contributions. The program worked by exploring a tree of possibilities: the root was the initial hypothesis, each branch a deduction drawn from logical rules, and the goal was a proposition somewhere in that tree. The path from root to goal was a proof. This framing, of problem-solving as navigation through a space of possibilities, became foundational to AI research.

  Newell and Simon recognized quickly that the search tree would grow exponentially. To manage it, they borrowed a term from George Pólya's book on mathematical proof, How to Solve It: "heuristics." These were rules of thumb for deciding which branches were unlikely to lead anywhere useful, allowing the program to trim the tree rather than exhaustively explore it. Newell had taken courses from Pólya at Stanford, which is where the connection came from. Heuristics became a major research area in AI and remain a central method for handling the combinatorial explosion of exponentially growing searches.

  To implement the program on an actual computer, the three researchers also built a programming language called IPL. It relied on symbolic list processing. That same approach would later form the basis of Lisp, the programming language John McCarthy developed and that AI researchers continued to use for decades after.

• 7. A Machine That Could Think

  ›

  Simon announced the achievement to a graduate class in January 1956 with a sentence that has since become well known: "Over Christmas, Al Newell and I invented a thinking machine." He later wrote that they had "invented a computer program capable of thinking non-numerically, and thereby solved the venerable mind-body problem, explaining how a system composed of matter can have the properties of mind."

  Philosopher John Searle would later name that position "Strong AI," the claim that machines can have minds in the same sense that people do. It remains a contested subject.

  Pamela McCorduck read Logic Theorist as something larger: the debut of a new theory of mind she called the information processing model, also known as computationalism or cognitivism. She wrote that this view would become central to Newell and Simon's later work, and that in their own judgment it was "as central to understanding mind in the 20th century as Darwin's principle of natural selection had been to understanding biology in the 19th century." Newell and Simon eventually formalized that claim as the physical symbol systems hypothesis. The program they built in 1956 was, by their own account, where that hypothesis first ran on actual hardware.