Logic Theorist
Encyclopedia
Logic Theorist is a computer program written in 1955 and 1956 by Allen Newell
, Herbert 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." 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.
did not yet exist. Even the term itself ("artificial intelligence") would not be coined until the following summer.
Herbert Simon
was a political scientist by training and 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.
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:
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:
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
.
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.
Heuristics : 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 eorge Pólya|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.
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.
Simon
famously told a graduate class in January 1956, "Over Christmas, Al Newell and I invented a thinking machine",
and would write:
This statement, that machines can have minds just as people do, would be later named "Strong AI" by philosopher John Searle
. It remains a serious subject of debate up to the present day.
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.
Allen Newell
Allen Newell was a researcher in computer science and cognitive psychology at the RAND corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department of Psychology...
, Herbert Simon
Herbert Simon
Herbert Alexander Simon was an American political scientist, economist, sociologist, and psychologist, and professor—most notably at Carnegie Mellon University—whose research ranged across the fields of cognitive psychology, cognitive science, computer science, public administration, economics,...
and J. C. Shaw
Cliff Shaw
J.C. Shaw was a systems programmer at the RAND Corporation. He is a coauthor of the first artificial intelligence program, the Logic Theorist, and was one of the developers of Information Processing Language, a programming language of the 1950s. It is considered the true "father" of the JOSS...
. It was the first program deliberately engineered to mimic the problem solving skills of a human being and is called "the first artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
program." It would eventually prove 38 of the first 52 theorems in Whitehead
Alfred North Whitehead
Alfred North Whitehead, OM FRS was an English mathematician who became a philosopher. He wrote on algebra, logic, foundations of mathematics, philosophy of science, physics, metaphysics, and education...
and Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
's Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...
, and find new and more elegant proofs for some.
History
In 1955, when Newell and Simon began to work on the Logic Theorist, the field of artificial intelligenceArtificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
did not yet exist. Even the term itself ("artificial intelligence") would not be coined until the following summer.
Herbert Simon
Herbert Simon
Herbert Alexander Simon was an American political scientist, economist, sociologist, and psychologist, and professor—most notably at Carnegie Mellon University—whose research ranged across the fields of cognitive psychology, cognitive science, computer science, public administration, economics,...
was a political scientist by training and had already produced classic work in the study of how bureaucracies
Bureaucracy
A bureaucracy is an organization of non-elected officials of a governmental or organization who implement the rules, laws, and functions of their institution, and are occasionally characterized by officialism and red tape.-Weberian bureaucracy:...
function as well as developed his theory of bounded rationality
Bounded rationality
Bounded rationality is the idea that in decision making, rationality of individuals is limited by the information they have, the cognitive limitations of their minds, and the finite amount of time they have to make a decision...
(for which he would later win a Nobel prize
Nobel Prize
The Nobel Prizes are annual international awards bestowed by Scandinavian committees in recognition of cultural and scientific advances. The will of the Swedish chemist Alfred Nobel, the inventor of dynamite, established the prizes in 1895...
). The study of business organizations may seem, on the surface, to be very different from artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
, but it requires the same insight into the nature of human problem solving and decision making
Decision theory
Decision theory in economics, psychology, philosophy, mathematics, and statistics is concerned with identifying the values, uncertainties and other issues relevant in a given decision, its rationality, and the resulting optimal decision...
. Simon remembers consulting at RAND
RAND
RAND Corporation is a nonprofit global policy think tank first formed to offer research and analysis to the United States armed forces by Douglas Aircraft Company. It is currently financed by the U.S. government and private endowment, corporations including the healthcare industry, universities...
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
Allen Newell
Allen Newell was a researcher in computer science and cognitive psychology at the RAND corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department of Psychology...
, a RAND Corporation scientist studying logistics
Logistics
Logistics is the management of the flow of goods between the point of origin and the point of destination in order to meet the requirements of customers or corporations. Logistics involves the integration of information, transportation, inventory, warehousing, material handling, and packaging, and...
and organization theory. For Newell, the decisive moment was in 1954 when Oliver Selfridge
Oliver Selfridge
Oliver Gordon Selfridge , grandson of Harry Gordon Selfridge, the founder of Selfridges' department stores, was a pioneer of artificial intelligence. He has been called the "Father of Machine Perception."...
came to RAND
RAND
RAND Corporation is a nonprofit global policy think tank first formed to offer research and analysis to the United States armed forces by Douglas Aircraft Company. It is currently financed by the U.S. government and private endowment, corporations including the healthcare industry, universities...
to describe his work on pattern matching
Pattern matching
In computer science, pattern matching is the act of checking some sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact. The patterns generally have the form of either sequences or tree structures...
. 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
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
and Alfred North Whitehead
Alfred North Whitehead
Alfred North Whitehead, OM FRS was an English mathematician who became a philosopher. He wrote on algebra, logic, foundations of mathematics, philosophy of science, physics, metaphysics, and education...
's Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...
. They enlisted the help of computer programmer J. C. Shaw, also from RAND
RAND
RAND Corporation is a nonprofit global policy think tank first formed to offer research and analysis to the United States armed forces by Douglas Aircraft Company. It is currently financed by the U.S. government and private endowment, corporations including the healthcare industry, universities...
, 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
Cliff Shaw
J.C. Shaw was a systems programmer at the RAND Corporation. He is a coauthor of the first artificial intelligence program, the Logic Theorist, and was one of the developers of Information Processing Language, a programming language of the 1950s. It is considered the true "father" of the JOSS...
was able to run the program on the computer at RAND
RAND
RAND Corporation is a nonprofit global policy think tank first formed to offer research and analysis to the United States armed forces by Douglas Aircraft Company. It is currently financed by the U.S. government and private endowment, corporations including the healthcare industry, universities...
's Santa Monica facility.
In the summer of 1956, John McCarthy
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
, Marvin Minsky
Marvin Minsky
Marvin Lee Minsky is an American cognitive scientist in the field of artificial intelligence , co-founder of Massachusetts Institute of Technology's AI laboratory, and author of several texts on AI and philosophy.-Biography:...
, Claude Shannon and Nathan Rochester
Nathaniel Rochester (computer scientist)
Nathan Rochester designed the IBM 701, wrote the first assembler and participated in the founding of the field of artificial intelligence.- Early work :...
organized a conference on the subject of what they called "artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
" (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
Pamela McCorduck
Pamela McCorduck is the author of a number of books concerning the history and philosophical significance of artificial intelligence, the future of engineering and the role of women and technology. She is also the author of three novels. She is a contributor to Omni, New York Times, Daedalus, the...
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
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...
. The proof of theorem 2.85
Isosceles triangle theorem
In Euclidean geometry, the isosceles triangle theorem, also known as the pons asinorum, states that the angles opposite the two equal sides of an isosceles triangle are equal...
was actually more elegant than the proof produced laboriously by hand by Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
and Whitehead
Alfred North Whitehead
Alfred North Whitehead, OM FRS was an English mathematician who became a philosopher. He wrote on algebra, logic, foundations of mathematics, philosophy of science, physics, metaphysics, and education...
. Simon was able to show the new proof to Bertrand Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
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
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
programs and ideas, including GPS
General Problem Solver
General Problem Solver was a computer program created in 1959 by Herbert Simon, J.C. Shaw, and Allen Newell intended to work as a universal problem solver machine. Any formalized symbolic problem can be solved, in principle, by GPS. For instance: theorems proof, geometric problems and chess...
, Soar
Soar (cognitive architecture)
Soar is a symbolic cognitive architecture, created by John Laird, Allen Newell, and Paul Rosenbloom at Carnegie Mellon University, now maintained by John Laird's research group at the University of Michigan. It is both a view of what cognition is and an implementation of that view through a...
, and their unified theory of cognition
Unified theory of cognition
Unified Theories of Cognition is a 1990 book by Allen Newell. Newell argues for the need of a set of general assumptions for cognitive models that account for all of cognition: a 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
Search tree
In computer science, a search tree is a binary tree data structure in whose nodes data values are stored from some ordered set, in such a way that in-order traversal of the tree visits the nodes in ascending order of the stored values...
: the root was the initial hypothesis
Hypothesis
A hypothesis is a proposed explanation for a phenomenon. The term derives from the Greek, ὑποτιθέναι – hypotithenai meaning "to put under" or "to suppose". For a hypothesis to be put forward as a scientific hypothesis, the scientific method requires that one can test it...
, each branch was a deduction based on the rules of logic. Somewhere "up" the tree was the goal: the proposition
Proposition
In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...
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.
Heuristics : Newell
Allen Newell
Allen Newell was a researcher in computer science and cognitive psychology at the RAND corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department of Psychology...
and Simon
Herbert Simon
Herbert Alexander Simon was an American political scientist, economist, sociologist, and psychologist, and professor—most notably at Carnegie Mellon University—whose research ranged across the fields of cognitive psychology, cognitive science, computer science, public administration, economics,...
realized that the search tree
Search tree
In computer science, a search tree is a binary tree data structure in whose nodes data values are stored from some ordered set, in such a way that in-order traversal of the tree visits the nodes in ascending order of the stored values...
would grow exponentially
Exponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
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
George Pólya
George Pólya was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamental contributions to combinatorics, number theory, numerical analysis and probability theory...
in his classic book on mathematical proof
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
, How to Solve It
How to Solve It
How to Solve It is a small volume by mathematician George Pólya describing methods of problem solving.- Four principles :How to Solve It suggests the following steps when solving a mathematical problem:...
. (Allen Newell
Allen Newell
Allen Newell was a researcher in computer science and cognitive psychology at the RAND corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department of Psychology...
had taken courses from eorge Pólya|Pólya] at Stanford) Heuristics would become an important area of research in artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
and remains an important method to overcome the intractable combinatorial explosion
Combinatorial explosion
In administration and computing, a combinatorial explosion is the rapidly accelerating increase in lines of communication as organizations are added in a process...
of exponentially growing searches.
List processing : To implement Logic Theorist on a computer, the three researchers developed a programming language, IPL
Information Processing Language
Information Processing Language is a programming language developed by Allen Newell, Cliff Shaw, and Herbert Simon at RAND Corporation and the Carnegie Institute of Technology from about 1956...
, which used the same form of symbolic list processing that would later form the basis of John McCarthy
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
's Lisp programming language, an important language still used by AI researchers.
Philosophical implications
Pamela McCorduckPamela McCorduck
Pamela McCorduck is the author of a number of books concerning the history and philosophical significance of artificial intelligence, the future of engineering and the role of women and technology. She is also the author of three novels. She is a contributor to Omni, New York Times, Daedalus, the...
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
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
and our understanding of intelligence in general.
Simon
Herbert Simon
Herbert Alexander Simon was an American political scientist, economist, sociologist, and psychologist, and professor—most notably at Carnegie Mellon University—whose research ranged across the fields of cognitive psychology, cognitive science, computer science, public administration, economics,...
famously told a graduate class in January 1956, "Over Christmas, Al Newell and I invented a thinking machine",
and would write:
[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.
This statement, that machines can have minds just as people do, would be later named "Strong AI" by philosopher John Searle
John Searle
John Rogers Searle is an American philosopher and currently the Slusser Professor of Philosophy at the University of California, Berkeley.-Biography:...
. It remains a serious subject of debate up to the present day.
Pamela McCorduck
Pamela McCorduck
Pamela McCorduck is the author of a number of books concerning the history and philosophical significance of artificial intelligence, the future of engineering and the role of women and technology. She is also the author of three novels. She is a contributor to Omni, New York Times, Daedalus, the...
also sees in the Logic Theorist the debut of a new theory of the mind, the information processing
Information processing
Information processing is the change of information in any manner detectable by an observer. As such, it is a process which describes everything which happens in the universe, from the falling of a rock to the printing of a text file from a digital computer system...
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.