Logic Theorist is a computer program written in 1955 and 1956 by Allen Newell, Herbert A. Simon and J. C. Shaw. It was the first program deliberately engineered to mimic the problem solving skills of a human being and is called "the first artificial intelligence program."[a] It would eventually prove 38 of the first 52 theorems in Whitehead and Russell's Principia Mathematica, and find new and more elegant proofs for some.
In 1955, when Newell and Simon began to work on the Logic Theorist, the field of artificial intelligence did not yet exist. Even the term itself ("artificial intelligence") would not be coined until the following summer.[b]
Herbert A. Simon was a political scientist who had already produced classic work in the study of how bureaucracies function as well as developed his theory of bounded rationality (for which he would later win a Nobel prize). The study of business organizations may seem, on the surface, to be very different from artificial intelligence, but it requires the same insight into the nature of human problem solving and decision making. Simon remembers consulting at RAND in the early 1950s and seeing a printer typing out a map, using ordinary letters and punctuation as symbols. He realized that a machine that could manipulate symbols could just as well simulate decision making and possibly even the process of human thought.
The program that printed the map had been written by Allen Newell, a RAND Corporation scientist studying logistics and organization theory. For Newell, the decisive moment was in 1954 when Oliver Selfridge came to RAND to describe his work on pattern matching. Watching the presentation, Newell suddenly understood how the interaction of simple, programmable units could accomplish complex behavior, including the intelligent behavior of human beings. "It all happened in one afternoon," he would later say. It was a rare moment of scientific epiphany.
"I had such a sense of clarity that this was a new path, and one I was going to go down. I haven't had that sensation very many times. I'm pretty skeptical, and so I don't normally go off on a toot, but I did on that one. Completely absorbed in it—without existing with the two or three levels consciousness so that you're working, and aware that you're working, and aware of the consequences and implications, the normal mode of thought. No. Completely absorbed for ten to twelve hours."
Newell and Simon began to talk about the possibility of teaching machines to think. Their first project was a program that could prove mathematical theorems like the ones used in Bertrand Russell and Alfred North Whitehead's Principia Mathematica. They enlisted the help of computer programmer J. C. Shaw, also from RAND, to develop the program. (Newell says "Cliff was the genuine computer scientist of the three").
The first version was hand-simulated: they wrote the program onto 3x5 cards and, as Simon recalled:
In January 1956, we assembled my wife and three children together with some graduate students. To each member of the group, we gave one of the cards, so that each one became, in effect, a component of the computer program ... Here was nature imitating art imitating nature.
They succeeded in showing that the program could successfully prove theorems as well as a talented mathematician. Eventually Shaw was able to run the program on the computer at RAND's Santa Monica facility.
In the summer of 1956, John McCarthy, Marvin Minsky, Claude Shannon and Nathan Rochester organized a conference on the subject of what they called "artificial intelligence" (a term coined by McCarthy for the occasion). Newell and Simon proudly presented the group with the Logic Theorist and were somewhat surprised when the program received a lukewarm reception. Pamela McCorduck writes "the evidence is that nobody save Newell and Simon themselves sensed the long-range significance of what they were doing." Simon confides that "we were probably fairly arrogant about it all" and adds:
They didn't want to hear from us, and we sure didn't want to hear from them: we had something to show them! ... In a way it was ironic because we already had done the first example of what they were after; and second, they didn't pay much attention to it.
Logic Theorist soon proved 38 of the first 52 theorems in chapter 2 of the Principia Mathematica. The proof of theorem 2.85 was actually more elegant than the proof produced laboriously by hand by Russell and Whitehead. Simon was able to show the new proof to Bertrand Russell himself who "responded with delight." They attempted to publish the new proof in The Journal of Symbolic Logic but it was rejected on the grounds that a new proof of an elementary mathematical theorem was not notable, apparently overlooking the fact that one of the authors was a computer program.
Newell and Simon formed a lasting partnership, founding one of the first AI laboratories at Carnegie Tech and developing a series of influential artificial intelligence programs and ideas, including GPS, Soar, and their unified theory of cognition.
Logic Theorist's influence on AI
Logic Theorist introduced several concepts that would be central to AI research:
- Reasoning as search
- Logic Theorist explored a search tree: the root was the initial hypothesis, each branch was a deduction based on the rules of logic. Somewhere "up" the tree was the goal: the proposition the program intended to prove. The pathway along the branches that led to the goal was a proof – a series of statements, each deduced using the rules of logic, that led from the hypothesis to the proposition to be proved.
- Newell and Simon realized that the search tree would grow exponentially and that they needed to "trim" some branches, using "rules of thumb" to determine which pathways were unlikely to lead to a solution. They called these ad hoc rules "heuristics", using a term introduced by George Pólya in his classic book on mathematical proof, How to Solve It. (Allen Newell had taken courses from Pólya at Stanford). Heuristics would become an important area of research in artificial intelligence and remains an important method to overcome the intractable combinatorial explosion of exponentially growing searches.
- List processing
- To implement Logic Theorist on a computer, the three researchers developed a programming language, IPL, which used the same form of symbolic list processing that would later form the basis of John McCarthy's Lisp programming language, an important language still used by AI researchers.
Pamela McCorduck writes that the Logic Theorist was "proof positive that a machine could perform tasks heretofor considered intelligent, creative and uniquely human." And, as such, it represents a milestone in the development of artificial intelligence and our understanding of intelligence in general.
[We] invented a computer program capable of thinking non-numerically, and thereby solved the venerable mind-body problem, explaining how system composed of a matter can have the properties of mind.
Pamela McCorduck also sees in the Logic Theorist the debut of a new theory of the mind, the information processing model (sometimes called computationalism). She writes that "this view would come to be central to their later work, and in their opinion, as central to understanding mind in the twentieth century as Darwin's principle of natural selection had been to understanding biology in the nineteenth century." Newell and Simon would later formalize this proposal as the physical symbol systems hypothesis.
- Logic theorist is usually considered the first true AI program, although Arthur Samuel's checkers program is earlier. Christopher Strachey also wrote a checkers program in 1951.
- The term "artificial intelligence" was coined by John McCarthy in the proposal for the 1956 Dartmouth Conference. The conference is "generally recognized as the official birthdate of the new science," according to Daniel Crevier.
- Crevier 1993, p. 44.
- McCorduck 2004, p. 167.
- Crevier 1993, pp. 49–50.
- Crevier 1993, pp. 41–44.
- McCorduck 2004, p. 148.
- McCorduck 2004, pp. 157–158.
- McCorduck 2004, pp. 158–159.
- McCorduck 2004, p. 169.
- Crevier 1993, p. 45.
- McCorduck 2004, p. 124.
- Crevier 1993, p. 48.
- Crevier 1993, p. 49.
- Crevier 1993, p. 146.
- Crevier 1993, p. 43.
- Crevier 1993, pp. 46–48.
- McCorduck 2004, pp. 167–168.
- McCorduck 2004, p. 138.
- CMU Libraries: Problem Solving Research
- Crevier 1993, p. 46.
- McCorduck 2004, p. 127.
- Crevier, Daniel (1993), AI: The Tumultuous Search for Artificial Intelligence, New York, NY: BasicBooks, ISBN 0-465-02997-3, pp. 44–46.
- McCorduck, Pamela (2004), Machines Who Think (2nd ed.), Natick, MA: A. K. Peters, Ltd., ISBN 1-56881-205-1, pp. 161–170.
- Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2, p. 17.