HOME

TheInfoList



OR:

Logic Theorist is a computer program written in 1956 by
Allen Newell Allen Newell (March 19, 1927 – July 19, 1992) 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 ...
,
Herbert A. Simon Herbert Alexander Simon (June 15, 1916 – February 9, 2001) was an American political scientist, with a Ph.D. in political science, whose work also influenced the fields of computer science, economics, and cognitive psychology. His primary ...
, 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 Solve ...
. , 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 progra ...
and is called "the first
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
program". ''See § Philosophical implications'' It would eventually prove 38 of the first 52 theorems in Whitehead and Russell's ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers 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 intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
did not yet exist. Even the term itself ("artificial intelligence") would not be coined until the following summer. Simon was a
political scientist Political science is the science, scientific study of politics. It is a social science dealing with systems of governance and power, and the analysis of politics, political activities, political thought, political behavior, and associated c ...
who had already produced classic work in the study of how
bureaucracies The term bureaucracy () refers to a body of non-elected governing officials as well as to an administrative policy-making group. Historically, a bureaucracy was a government administration managed by departments staffed with non-elected offi ...
function as well as developed his theory of
bounded rationality Bounded rationality is the idea that rationality is limited when individuals make decisions, and under these limitations, rational individuals will select a decision that is satisfactory rather than optimal. Limitations include the difficulty of ...
(for which he would later win a
Nobel Prize The Nobel Prizes ( ; sv, Nobelpriset ; no, Nobelprisen ) are five separate prizes that, according to Alfred Nobel's will of 1895, are awarded to "those who, during the preceding year, have conferred the greatest benefit to humankind." Alfr ...
). The study of business organizations requires, like
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
, 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 rati ...
. Simon remembers consulting at
RAND Corporation The RAND Corporation (from the phrase "research and development") is an American nonprofit global policy think tank created in 1948 by Douglas Aircraft Company to offer research and analysis to the United States Armed Forces. It is financed ...
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 Newell, a RAND scientist studying
logistics Logistics is generally the detailed organization and implementation of a complex operation. In a general business sense, logistics manages the flow of goods between the point of origin and the point of consumption to meet the requirements of ...
and
organization theory Organizational theory refers to the set of interrelated concepts that involve the sociological study of the structures and operations of formal social organizations. Organizational theory also attempts to explain how interrelated units of organiz ...
. For Newell, the decisive moment was in 1954 when
Oliver Selfridge Oliver Gordon Selfridge (10 May 1926 – 3 December 2008) was a pioneer of artificial intelligence. He has been called the "Father of Machine Perception." Biography Selfridge, born in England, was a grandson of Harry Gordon Selfridge, the founde ...
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 has to be exact: "either it will or will not be ...
. 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 mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ...
and
Alfred North Whitehead Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician and philosopher. He is best known as the defining figure of the philosophical school known as process philosophy, which today has found applicat ...
's ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
''. 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 Solve ...
, 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 and computer scientist concerned largely with research of artificial intelligence (AI), co-founder of the Massachusetts Institute of Technology's AI laboratory, an ...
,
Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory". As a 21-year-o ...
and Nathan Rochester organized a conference on the subject of what they called "
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
" (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 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 mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
''. 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 persons or things already mentioned, under discussion, implied or otherwise presumed familiar to listeners, readers, or speakers. It is the definite article in English. ''The'' is the m ...
'' 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. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
and developing a series of influential
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
programs and ideas, including
GPS The Global Positioning System (GPS), originally Navstar GPS, is a Radionavigation-satellite service, satellite-based radionavigation system owned by the United States government and operated by the United States Space Force. It is one of t ...
, Soar, and their
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, or cognitive architecture. The res ...
.


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 less ...
: the root was the initial
hypothesis A hypothesis (plural hypotheses) is a proposed explanation for a phenomenon. For a hypothesis to be a scientific hypothesis, the scientific method requires that one can test it. Scientists generally base scientific hypotheses on previous obse ...
, each branch was a deduction based on the rules of logic. Somewhere in the tree was the goal: the
proposition In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...
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 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 less ...
would grow
exponentially Exponential may refer to any of several mathematical topics related to exponentiation, including: *Exponential function, also: **Matrix exponential, the matrix analogue to the above * Exponential decay, decrease at a rate proportional to value *Exp ...
and that they needed to "trim" some branches, using "
rules of thumb In English, the phrase ''rule of thumb'' refers to an approximate method for doing something, based on practical experience rather than theory. This usage of the phrase can be traced back to the 17th century and has been associated with various t ...
" to determine which pathways were unlikely to lead to a solution. They called these ''ad hoc'' rules "
heuristics A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
", using a term introduced by
George Pólya George Pólya (; hu, Pólya György, ; December 13, 1887 – September 7, 1985) 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 ...
in his classic book on
mathematical proof A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proo ...
, ''
How to Solve It ''How to Solve It'' (1945) 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: # First, you have to ''un ...
''. (Newell had taken courses from Pólya at
Stanford Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is considere ...
). Heuristics would become an important area of research in
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech 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 how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used ...
of exponentially growing searches. ;List processing : To implement Logic Theorist on a computer, the three researchers developed a programming language,
IPL The Indian Premier League (IPL), also known as TATA IPL for sponsorship reasons, is a men's T20 franchise cricket league of India. It is annually contested by ten teams based out of seven Indian cities and three Indian states. The leagu ...
, which used the same form of symbolic list processing that would later form the basis of McCarthy's
Lisp A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech. Types * A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lisping ...
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 intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
and our understanding of intelligence in general.
Simon Simon may refer to: People * Simon (given name), including a list of people and fictional characters with the given name Simon * Simon (surname), including a list of people with the surname Simon * Eugène Simon, French naturalist and the genus ...
famously 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.
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 Information processing is the change (processing) of information in any manner detectable by an observer. As such, it is a process that ''describes'' everything that happens (changes) in the universe, from the falling of a rock (a change in posit ...
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 ...
). 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 The 20th (twentieth) century began on January 1, 1901 ( MCMI), and ended on December 31, 2000 ( MM). The 20th century was dominated by significant events that defined the modern era: Spanish flu pandemic, World War I and World War II, nuclear ...
as Darwin's principle of natural selection had been to understanding biology in the
nineteenth century The 19th (nineteenth) century began on 1 January 1801 ( MDCCCI), and ended on 31 December 1900 ( MCM). The 19th century was the ninth century of the 2nd millennium. The 19th century was characterized by vast social upheaval. Slavery was abolish ...
." Newell and Simon would later formalize this proposal as the
physical symbol systems hypothesis A physical symbol system (also called a formal system) takes physical patterns (symbols), combining them into structures (expressions) and manipulating them (using processes) to produce new expressions. The physical symbol system hypothesis (PSSH ...
.


Notes


Citations


References

* , pp. 44–46. * , pp. 161–170. * {{Russell Norvig 2003, p. 17.


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