HOME

TheInfoList



OR:

Logic Theorist is a computer program written in 1956 by
Allen Newell Allen Newell (March 19, 1927 – July 19, 1992) was an American 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 D ...
,
Herbert A. Simon Herbert Alexander Simon (June 15, 1916 – February 9, 2001) was an American scholar whose work influenced the fields of computer science, economics, and cognitive psychology. His primary research interest was decision-making within organi ...
, and
Cliff Shaw John Clifford Shaw (February 23, 1922 – February 9, 1991) 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 General Problem Sol ...
. , and It was the first program deliberately engineered to perform
automated reasoning In computer science, in particular in knowledge representation and reasoning and metalogic, the area of automated reasoning is dedicated to understanding different aspects of reasoning. The study of automated reasoning helps produce computer progr ...
, and has been described as "the first
artificial intelligence Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
program". Logic Theorist proved 38 of the first 52 theorems in chapter two of Whitehead and
Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British philosopher, logician, mathematician, and public intellectual. He had influence on mathematics, logic, set theory, and various areas of analytic ...
's ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by the mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1 ...
'', and found new and shorter proofs for some of them.


History

In 1955, when Newell and Simon began to work on the Logic Theorist, the field of
artificial intelligence Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
did not yet exist; the term "artificial intelligence" would not be coined until the following summer. Simon was a
political scientist Political science is the scientific study of politics. It is a social science dealing with systems of governance and Power (social and political), power, and the analysis of political activities, political philosophy, political thought, polit ...
who had previously studied the way bureaucracies function as well as developing his theory of
bounded rationality Bounded rationality is the idea that rationality is limited when individuals decision-making, make decisions, and under these limitations, rational individuals will select a decision that is satisficing, satisfactory rather than optimal. Limitat ...
(for which he would later win a Nobel Prize). He believed the study of business organizations requires, like artificial intelligence, an insight into the nature of human problem solving and
decision making In psychology, decision-making (also spelled decision making and decisionmaking) is regarded as the cognitive process resulting in the selection of a belief or a course of action among several possible alternative options. It could be either ra ...
. Simon has stated that when consulting at
RAND Corporation The RAND Corporation, doing business as RAND, is an American nonprofit global policy think tank, research institute, and public sector consulting firm. RAND engages in research and development (R&D) in several fields and industries. Since the ...
in the early 1950s, he saw a printer typing out a map, using ordinary letters and punctuation as symbols. This led him to think that a machine that could manipulate symbols could simulate decision making and possibly even the process of human thought. The program that printed the map had been written by Newell, a RAND scientist studying logistics and
organization theory Organizational theory refers to a series of interrelated concepts that involve the sociological study of the structures and operations of formal social organizations. Organizational theory also seeks to explain how interrelated units of organiza ...
. For Newell, the decisive moment was in 1954 when Oliver Selfridge came to RAND to describe his work on
pattern matching In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually must be exact: "either it will or will not be a ...
. 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 Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British philosopher, logician, mathematician, and public intellectual. He had influence on mathematics, logic, set theory, and various areas of analytic ...
and
Alfred North Whitehead Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician and philosopher. He created the philosophical school known as process philosophy, which has been applied in a wide variety of disciplines, inclu ...
's ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by the mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1 ...
''. They enlisted the help of computer programmer
Cliff Shaw John Clifford Shaw (February 23, 1922 – February 9, 1991) 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 General Problem Sol ...
, 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 Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive scientist, cognitive and computer scientist concerned largely with research in artificial intelligence (AI). He co-founded the Massachusetts Institute of Technology ...
,
Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, computer scientist, cryptographer and inventor known as the "father of information theory" and the man who laid the foundations of th ...
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. It was met with a lukewarm reception.
Pamela McCorduck Pamela Ann McCorduck (October 27, 1940 – October 18, 2021) was a British-born American author of books about the history and philosophical significance of artificial intelligence, the future of engineering, and the role of women and technolog ...
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 ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by the mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1 ...
''. 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 Russell himself who "responded with delight". They attempted to publish the new proof in ''
The Journal of Symbolic Logic ''The'' is a grammatical article in English, denoting nouns that are already or about to be mentioned, under discussion, implied or otherwise presumed familiar to listeners, readers, or speakers. It is the definite article in English. ''The ...
'', 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 the
Carnegie Institute of Technology Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania, United States. The institution was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools. In 1912, it became the Carnegie Institu ...
and developing a series of influential artificial intelligence programs and ideas, including the
General Problem Solver General Problem Solver (GPS) is a computer program created in 1957 by Herbert A. Simon, J. C. Shaw, and Allen Newell ( RAND Corporation) intended to work as a universal problem solver machine. In contrast to the former Logic Theorist project, ...
, Soar, and their unified theory of cognition.


Architecture

The Logic Theorist is a program that performs logical ''processes'' on logical ''expressions''. The Logic Theorist operates on the following principles:


Expressions

* An expression is made of ''elements''. * There are two kinds of memories: ''working'' and ''storage''. * Each working memory contains a single element. The Logic Theorist usually uses 1 to 3 working memories. * Each storage memory is a list representing a full expression or a set of elements. In particular, it contains all the axioms and proven logical theorems. * An expression is an
abstract syntax tree An abstract syntax tree (AST) is a data structure used in computer science to represent the structure of a program or code snippet. It is a tree representation of the abstract syntactic structure of text (often source code) written in a formal ...
, each node being an element with up to 11 attributes. For example, the logical expression \neg P \to (Q \wedge \neg P) is represented as a tree with a root element representing \to. Among the attributes of the root element are pointers to the two elements representing the subexpressions \neg P and Q \wedge \neg P.


Processes

There are four kinds of processes, from the lowest to the highest level. * Instruction: These are similar to
assembly code In computing, assembly language (alternatively assembler language or symbolic machine code), often referred to simply as assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence bet ...
. They may either perform a primitive operation on an expression in working memory, or perform a conditional jump to another instruction. An example is "put the right sub-element of working-memory 1 to working-memory 2" * Elementary process: These are similar to subroutines. A sequence of instructions that can be called. * Method: A sequence of elementary processes. There are 4 methods: ** substitution: given an expression, it attempts to transform it to a proven theorem or axiom by substitutions of variables and logical connectives. ** detachment: given expression B, it attempts to find a proven theorem or axiom of form A \to B', where B' yields B after substitution, then attempts to prove A by substitution. ** chaining forward: given expression A\to C, it attempts to find for a proven theorem or axiom of form A\to B, then attempt to prove B \to C by substitution. ** chaining backward: given expression A\to C, it attempts to find for a proven theorem or axiom of form B \to C, then attempt to prove A\to B by substitution. * executive control method: This method applies each of the 4 methods in sequence to each theorem to be proved.


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 In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and les ...
: the root was the initial
hypothesis A hypothesis (: hypotheses) is a proposed explanation for a phenomenon. A scientific hypothesis must be based on observations and make a testable and reproducible prediction about reality, in a process beginning with an educated guess o ...
, each branch was a deduction based on the rules of logic. Somewhere in the tree was the goal: the
proposition A proposition is a statement that can be either true or false. It is a central concept in the philosophy of language, semantics, logic, and related fields. Propositions are the object s denoted by declarative sentences; for example, "The sky ...
the program intended to prove. The pathway along the branches that led to the goal was a
proof Proof most often refers to: * Proof (truth), argument or sufficient evidence for the truth of a proposition * Alcohol proof, a measure of an alcoholic drink's strength Proof may also refer to: Mathematics and formal logic * Formal proof, a co ...
 – 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 In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and les ...
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 A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
", using a term introduced by
George Pólya George Pólya (; ; December 13, 1887 – September 7, 1985) was a Hungarian-American 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 contributi ...
in his classic book on
mathematical proof A mathematical proof is a deductive reasoning, deductive Argument-deduction-proof distinctions, argument for a Proposition, mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use othe ...
, ''
How to Solve It ''How to Solve It'' (1945) is a small volume by mathematician George Pólya, describing methods of problem solving. This book has remained in print continually since 1945. Four principles ''How to Solve It'' suggests the following steps ...
''. (Newell had taken courses from Pólya at
Stanford Leland Stanford Junior University, commonly referred to as Stanford University, is a private research university in Stanford, California, United States. It was founded in 1885 by railroad magnate Leland Stanford (the eighth governor of and th ...
). Heuristics would become an important area of research in
artificial intelligence Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
and remains an important method to overcome the intractable
combinatorial explosion In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to the way its combinatorics depends on input, constraints and bounds. Combinatorial explosion is sometimes used to justify the intractability of cert ...
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 McCarthy's
Lisp Lisp (historically LISP, an abbreviation of "list processing") is a family of programming languages with a long history and a distinctive, fully parenthesized Polish notation#Explanation, prefix notation. Originally specified in the late 1950s, ...
programming language, an important language still used by AI researchers.


Philosophical implications

Pamela McCorduck Pamela Ann McCorduck (October 27, 1940 – October 18, 2021) was a British-born American author of books about the history and philosophical significance of artificial intelligence, the future of engineering, and the role of women and technolog ...
writes that the Logic Theorist was "proof positive that a machine could perform tasks heretofore considered intelligent, creative and uniquely human". And, as such, it represents a milestone in the development of
artificial intelligence Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
and our understanding of intelligence in general. Simon told a graduate class in January 1956, "Over Christmas, Al Newell and I invented a thinking machine," and would write:
e/nowiki> 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.Quoted in
This statement, that machines can have minds just as people do, would be later named " Strong AI" by philosopher
John Searle John Rogers Searle (; born July 31, 1932) is an American philosopher widely noted for contributions to the philosophy of language, philosophy of mind, and social philosophy. He began teaching at UC Berkeley in 1959 and was Willis S. and Mario ...
. It remains a serious subject of debate up to the present day.
Pamela McCorduck Pamela Ann McCorduck (October 27, 1940 – October 18, 2021) was a British-born American author of books about the history and philosophical significance of artificial intelligence, the future of engineering, and the role of women and technolog ...
also sees in the Logic Theorist the debut of a new theory of the mind, the
information processing In cognitive psychology, information processing is an approach to the goal of understanding human thinking that treats cognition as essentially Computing, computational in nature, with the mind being the ''software'' and the brain being the ''hard ...
model (sometimes called
computationalism In philosophy of mind, the computational theory of mind (CTM), also known as computationalism, is a family of views that hold that the human mind is an information processing system and that cognition and consciousness together are a form of comp ...
or cognitivism). 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 20th 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.


Notes


Citations


References

* , pp. 44–46. * , pp. 161–170. * {{Cite book , first1 = Stuart J. , last1 = Russell , author1-link = Stuart J. Russell , first2 = Peter. , last2 = Norvig , author2-link = Peter Norvig , title= Artificial Intelligence: A Modern Approach , year = 2021 , edition = 4th , isbn = 9780134610993 , lccn = 20190474 , publisher = Pearson , location = Hoboken


External links


Newell and Simon's RAND Corporation report on the Logic Theorist

Full length version of Newell and Simon's RAND Corporation report on the Logic Theorist



Source code as PDF on Github
History of artificial intelligence Theorem proving software systems