Allen Newell

Gualtiero Piccinini

 

This is a preprint of an article whose final and definitive form will be published in New Dictionary of Scientific Biography, Thomson Gale.

 

Newell, Allen (b. San Francisco, California, 19 March 1927; d. Pittsburgh, Pennsylvania, 19 July 1992), computer science, artificial intelligence, cognitive psychology.

            Newell was a founder of artificial intelligence (AI) and a pioneer in the use of computer simulations in psychology.  In collaboration with J. Cliff Shaw and Herbert A. Simon, Newell developed the first list-processing programming language as well as the earliest computer programs for simulating human problem solving.  Over a long and prolific career, he contributed to many techniques, such as protocol analysis and heuristic search, that are now part of psychology and computer science.  Colleagues remembered Newell for his deep commitment to science, his care for details, and his inexhaustible energy.

 

Education

Newell was the second and youngest son of Jeanette Le Valley Newell and Robert R. Newell, a professor of radiology at Stanford Medical School.  At 16, Allen Newell fell in love with Noël McKenna, a fellow high school student.  They got married four years later and had a son, Paul.

            Although he admired his father, whom he described as a “complete man,” Newell did not grow up planning to be a scientist.  After completing one quarter at Stanford University, at the end of WWII, he was drafted into the Navy.  His father, Robert Newell, belonged to a team of scientists involved in the study of the Bikini Atoll nuclear tests.  Robert asked that his son Allen be assigned to assist the team.  Allen’s contribution was to write maps of the radiation distribution over the atolls.  This exciting endeavor turned Allen on to science.  Back from the Navy, he reenrolled in Stanford University, where he majored in physics.  Still fascinated with radiation, he spent much of his college time working on x-ray microscopy as a research assistant.

            As a freshman, Newell took a course in which George Polya, a distinguished mathematician, covered his book, How to Solve It (1945).  Newell was so fascinated with Polya that he took many more courses with him.  Polya’s book is on heuristics—plausible methods for solving problems.  Unlike algorithmic methods, which are always guaranteed to solve every solvable instance of a problem, heuristic methods may or may not lead to the best solution.  But for many problems, algorithms are either unavailable or impractical.  In such cases, heuristic methods are needed.  Heuristic methods played a critical role in Newell’s later research.

            In 1949, Newell went from Stanford to Princeton, to pursue graduate studies in mathematics.  As a research associate for Oskar Morgenstern, he worked on stochastic models of logistic problems and on game theory, which had recently been invented by Morgenstern with John von Neumann.  But pure mathematics was not for Newell.  By the end of his first year, he left Princeton for a job at RAND Corporation in Santa Monica, California.  RAND was a recently founded think tank, devoted to research with military applications and funded mainly by the Air Force.  As a member of RAND’s Mathematics Division, Newell was free to pursue research that interested him.  He could also collaborate with the many talented scientists who worked at RAND as well as dozens of external consultants who visited every summer.

 

RAND Corporation

RAND provided Newell with several formative experiences.  With Joseph B. Kruskal, he co-authored two reports, in which they applied formal game-theoretic methods to organization theory.  He spent six weeks in Washington, D.C., visiting the Munitions Board, which was responsible for logistics at the Pentagon.  Upon return, he wrote a report proposing a research program for the “science of supply”.  He also designed and conducted experiments on decision-making in small groups, experiments along the lines of those by Fred Bales, a Harvard social psychologist and RAND consultant.  Eventually, Newell joined an ambitious team of psychologists devoted to the experimental study of human organizational behavior.

            Besides Newell, the group consisted of William C. Biel, Robert Chapman, and John L. Kennedy.  They built and studied a full-scale simulation of an Air Defense Early Warning Station, whose crew had to observe radar signals and decide whether to send planes to investigate them.  The simulation was aimed at understanding the crew’s interactions with radar screens, interception aircraft, and each other.  The technique for doing so, which involved tape recording and analyzing the crew’s phone conversations, prefigured Newell’s later work on human thinking-aloud protocols.  This research led to a training program for the Air Defense Command and to the creation of the System Development Corporation to implement it.  For security reasons, the group published little.  Nevertheless, for this work, Biel, Chapman, Kennedy, and Newell shared the 1979 Alexander C. Williams, Jr., Award from the Human Factors Society.

            Within the group, Newell was in charge of simulating air traffic radar displays, which had to be realistic and continuously evolving in time.  To do so, he enlisted the help of Cliff Shaw, a RAND programmer who became a long-term collaborator.  Newell and Shaw programmed an IBM Card-Programmed Calculator to generate the successive radar displays, based on data from actual flight patterns.  This gave them early experience with using computing machines for non-numerical tasks—an activity that became paramount to Newell’s research.

            This was the heyday of cybernetics, information theory, and automata theory.  The first modern computers were being built, and a hot new idea was the analogy between mental and computational processes.  The analogy was initially proposed by Warren S. McCulloch and Walter Pitts.  It was quickly adopted and developed by Norbert Wiener, John von Neumann, and other scientists, whose work would have an impact on Newell.

In 1936, Alan M. Turing proposed a formal model of computation that became the foundation of theoretical computer science.  In 1943, McCulloch and Pitts argued that neurons were simple logic devices such that mental processes could be explained by computations performed by the brain.  In the late 1940s, several laboratories, including one at RAND, began building modern digital computers—“electronic brains,” as they became popularly known.  In 1948, Norbert Wiener’s Cybernetics offered a vision for a new science of minds and machines, and the publication of Claude Shannon’s mathematical theory of information generated considerable excitement.  In 1950, Turing argued that computers could be programmed to behave as intelligently as humans, although Newell didn’t find out about this until much later.  In 1952, Ross Ashby offered an influential synthesis of these ideas in his book, Design for a Brain.  In 1949, William Grey-Walter built mechanical turtles that plugged themselves into electrical outlets when their batteries ran low; a version of them could be seen crawling around RAND offices.  By the early 1950s, several people took steps towards AI:  Turing and Shannon sketched designs for chess-playing computers, Arthur Samuel programmed a computer to play checkers, and Oliver Selfridge and G. P. Dinneen wrote computer programs to do pattern recognition and learning.  During his five years of residence at RAND, Newell absorbed these new ideas, which were ushering in the information-processing revolution and the birth of AI.

            Another man attracted by this new culture of information processing and automata was Herbert Simon, who was then an established social scientist at Carnegie Institute of Technology (now Carnegie Mellon University), in Pittsburgh, Pennsylvania.  Simon was a consultant for Newell’s group at RAND.  The two clicked and became lifelong friends.  In 1954, Newell decided to move to Pittsburgh and write a Ph.D. dissertation under Simon.  Before leaving RAND, Newell attended a seminar by Selfridge on his work with Dinneen on computer learning and pattern recognition.  Impressed with Selfridge’s demonstration that a computer could exhibit such intelligent behavior, Newell had what he described as a “conversion experience”.  He envisioned programming computers to act as intelligent agents.  He decided to devote all his energies to the task of understanding the human mind by simulating it.  This remained the primary focus of his research through the rest of his life.

 

Computers as Intelligent Agents

Newell immediately began working on his new research program.  During the following four months, he wrote a computer program designed to play chess in a way that resembled human playing.  The program was a step towards Newell’s characteristic methodology of cognitive simulation:  drawing ideas from psychology in programming and understanding the mind by building one.  With Simon, he later argued that a program that simulates a cognitive process constitutes a rigorous theory of the process, and that psychological theories should be accompanied by computer simulations.  Newell did not manage to implement his first chess program, but some of his ideas came to fruition in a later chess program (1958).

            In 1955, while remaining affiliated with RAND, Newell moved to Carnegie Tech.  He defended his dissertation in 1957 and became Institute Professor in 1961.  He never moved again—he stayed at Carnegie Tech (later Carnegie Mellon University) even during sabbaticals.

            The last five years of the 1950’s saw Newell—together with Shaw (still at RAND) and Simon—producing the work on AI that propelled the Carnegie-RAND group to international fame:  Logic Theorist, General Problem Solver, list processing, and protocol analysis.

            Logic Theorist (LT) was designed to discover proofs of the logical theorems contained in Chapter 2 of Alfred N. Whitehead and Bertrand Russell’s Principia Mathematica (1910-1913).  LT represented axioms and theorems by symbolic structures (called states) and modified them by applying suitable operators.  But LT did not attempt every combination of symbols and operators—there wasn’t enough speed and memory for that.  Also, its method was not designed to find proofs in the most efficient way possible.  Rather, LT’s heuristic method attempted to mimic human discovery:  it started with the theorem to be proved, and then it searched for axioms and operators from which to derive the theorem.  It managed to prove 38 out of 52 theorems.

            LT was simulated by hand in December 1955 and produced the first mechanical proof of a theorem on 9 August 1956.  It was the only running program presented at the Dartmouth Conference of 1956—the first conference explicitly devoted to AI.  It was the first mechanical theorem-prover.  It was part of an ambitious research program of simulating human thinking.  And it came with a novel way to program computers.

            At the time, there were no high-level programming languages.  Computers were programmed in a language very close to the 1’s and 0’s manipulated by the processor.  This made it difficult to define non-numerical symbolic structures, like the logical formulae manipulated by LT.  Furthermore, computer memories were very small.  This made it difficult to use computers for tasks, such as heuristic search, that required a varying and unpredictable amount of memory.  To overcome these and other obstacles, Newell and his collaborators invented the first list-processing language.  A list is like a simple associative memory, in which one symbol has a link to another, which links to another, and so on.  In list processing, the lists—the symbols and links—are created and modified to generate structures of (in principle) unlimited length and complexity.  Many of the ideas introduced with list processing became fundamental to computer science.  And one of the Dartmouth organizers, John McCarthy, went on to write Lisp, an improved list-processing language that became standard in AI.

            To develop and test models of human thinking, data were needed.  Neuroscience was not advanced enough to provide them, and introspection was considered unreliable.  Mainstream experimental psychologists recorded only behaviors and reaction times during simple tasks, without asking subjects for clues as to what they were thinking.  To Newell and Simon, these traditional data sources seemed insufficient to understand human problem solving.  Hence, they revived introspection in the form of protocol analysis.  They asked subjects to think aloud while doing their logical derivation or other task and recorded their subjects’ speech.  They devised procedures for both extracting information about thought processes from the protocols and testing the validity of the protocols.  Protocol analysis provided the main ground for testing the accuracy of Newell and Simon’s simulations, and it expanded the range of evidence available to psychologists.

            In 1957, by analyzing the protocol of a subject doing logic derivations, Newell and Simon discovered a general heuristic method for solving problems.  They dubbed it means-ends analysis:  a subject compares the current state of the problem with a goal state (the ends), finds the difference between them, searches in memory for operators that might reduce this kind of difference (the means), and applies them to the current state.  The process is repeated until either all differences are eliminated—and the problem is solved—or the subject gives up.  In the latter case, the available resources (operators, time, etc.) have been used but the problem remains unsolved.

            Means-ends analysis became the core of a theory of human problem solving and of General Problem Solver (GPS), a program that was more powerful and general than LT and other AI programs at the time.  Unlike LT, which specialized in logical theorems, GPS could solve problems in different domains.  All it needed was a way to represent the domain, operators for manipulating the representations, and information about which operators could reduce which differences.  To some extent, GPS could even construct new operators from a set of primitives and learn which operators reduced which differences.  After GPS, means-ends analysis became widely used in AI.

            Sometimes, GPS would get lost in the search for a solution to a sub-problem, digging itself into a processing hole without exit.  The Carnegie-RAND group thought this pitfall might be addressed by writing into each operator the conditions for its correct application.  This way, operators could be applied to relevant situations without requiring searches that risked being endless.  Each instruction would take the form of an if-then statement—“if things are so and so, then do such and such”—and would be applied automatically just in case its conditions were satisfied.  The result of each operation would be deposited in a central memory storage, or working memory, on which all operators could write.  Instructions of this if-then form are called productions and constitute production systems, a general programming style invented by logician Emil Post (1943) and adapted to computer science by Robert Floyd (1961).  Newell took production systems to heart as a potent new way of programming.  He developed a succession of production system languages, which he and others used to build AI systems.

 

Unified Theories of Cognition

From the 1960s on, Newell participated in many collaborative research projects in computer science.  One of the most significant projects led to a technique for comparing computer architectures.  Architecture is the set of fixed mechanisms and organizing principles of a computer.  Together with the software that runs on it, a computer’s architecture explains its behavior.  In 1968, Newell agreed to help Gordon Bell write a textbook on computer architectures (first edition, 1972; revised edition, with Dan Siewiorek, 1981). 

            In order to classify and compare different computer architectures, Newell and Bell distinguished different levels of analysis—descriptions of computers and their behavior containing different amounts of detail—and devised general languages for two important levels.  One was the system level, which is constituted by the main components of a computer, such as processors, memories, and links between them.  The other was the instruction level, which is constituted by the primitive operations performed by a processor and the set of primitive instructions that drive them.  Newell and Bell’s language for the instruction level, ISP, later made it possible for different computers to simulate each other.  As long as one computer had an ISP description and another could run an interpreter for ISP, the second computer could simulate the first by running its ISP description.

            Another important project developed by Newell led to a theory of human-computer interaction.  In 1970, the Xerox Palo Alto Research Center—a center on digital technology—was formed in Palo Alto, California.  Newell, a consultant for the center, proposed to study the way users interact with computers.  So in 1974, Stuart Card and Thomas Moran—two students of Newell’s—moved to Palo Alto.  Together with Newell, they collected a wide range of psychological data and theories—such as Fitts’s Law, the power law of learning, and models of human typing—and unified them into a general model of routine cognitive skills that could be used by designers of computer interfaces (published in 1983). 

            The model described the human cognitive architecture, which was assumed to include perceptual, motor, and cognitive processors as well as memories to store data.  The model estimated the main functional characteristics of the components, such as the time required for a processor’s cycle and the size of the memories.  The model was also associated with a methodology for analyzing a computer user’s routine task, separating the task into the basic processes necessary to perform it.  By using this methodology, a designer could approximately predict the time it would take a user to perform a certain routine task, such as typing a piece of text or using the mouse to reach a target.  Modeling the routine cognitive skills of human beings required a synthesis of many psychological data and theories.  This provided a blueprint and some impetus for Newell’s final and most ambitious project:  a theory of the widest possible range of psychological phenomena, a unified theory of cognition.

            Newell saw the science of psychology as fragmented:  practitioners specialized in a narrow range of phenomena, such as some aspect of perception, memory, or reasoning; perhaps, they even developed a specialized theory to explain the phenomena.  But starting in the 1970s, Newell argued that psychologists could aim higher.

            Newell saw minds and computers as knowledge systems, namely, systems that may be understood in terms of the content of their beliefs and goals.  At the knowledge level—the most abstract level of analysis for intelligent systems—behavior is predicted and explained by assuming that the system pursues goals in light of its beliefs.  According to Newell, knowledge systems are implemented—always imperfectly—by physical symbol systems, i.e., systems that generate behavior by executing programs on symbolic structures.  From his extensive experience with artificial computers, he knew that computers could be understood in terms of their architecture—the fixed mechanisms—plus their programs—the software.  Newell argued that the human mind could be understood in the same way, provided that psychologists go beyond their narrow specializations and bring existing psychological data and theories to bear on the nature of the human cognitive architecture.

            As a vehicle for his unified theory of cognition, Newell chose Soar, a production systems architecture for general intelligence that he and his students John Laird and Paul Rosenbloom began working on towards the beginning of the 1980’s.

            The core of Soar as a unified theory is a general-purpose problem solver.  To a first approximation, it is a production systems version of GPS.  The system learns by chunking, a notion that takes George Miller’s classic notion of an information chunk (1956) and extends it to procedural learning:  after it solves a problem, Soar creates a new instruction in the form of a production, which summarizes what needs to be done to solve that problem.  The next time it encounters that problem, Soar may use this new production, without having to solve the problem anew.  Thus, Soar’s chunking explains some types of learning.

            In developing his unified theory, Newell took into account as many architectural constraints as possible:  from neuroscience (size and speed of components), from psychology (behaviors and reaction times), and from computer science (features of symbol processing).  He and his collaborators developed their theory into explanations of many psychological phenomena at many temporal scales, from simple behaviors, such as pressing a button when a light goes on, to solving difficult problems, such as solving cryptarithmetic puzzles.  Although Newell’s unified theory aims at bridging levels and satisfying multiple constraints, Newell did not attempt to explain how the architecture he proposed may be implemented in the human brain.

            Newell subsumed much of his previous work—on problem solving, on human-computer interaction, and on computer architectures—within Soar as a unified theory.  In addition, many important psychological phenomena and some influential mid-range theories (such as Philip Johnson-Laird’s theory of mental models) found a place within Soar.  Newell worked on Soar until his death.  After that, work continued in several laboratories around the world.  Soar made possible the creation of virtual human beings, such as synthetic pilots that behaved as much as possible like human pilots.

            Newell led the development of computer science, AI, and cognitive science as both disciplines and institutions.  His peers recognized his role in research and service.  His long list of honors includes the following:  in 1971, the Harry Goode Memorial Award of the American Federation of Information Processing Societies; in 1975, the A. M. Turing Award of the Association of Computing Machinery (with Herbert Simon); in 1980, being the founding president of the American Association for Artificial Intelligence; in 1985, the Distinguished Scientific Contribution Award of the American Psychological Association; in 1992, one month before he died of cancer at age 65, the National Medal of Science.

 

Acknowledgements: Thanks to Margaret Boden, John Gabriel, John Laird, and Paul Rosenbloom.  Preparation of this article was supported by the National Endowment for the Humanities and a Research Award from the University of MissouriSt. Louis.  The views expressed here do not necessarily reflect those of these institutions.

 

Bibliography

Works By Newell:

“Allen Newell Collection.” Carnegie Mellon University Archives. Available from http://diva.library.cmu.edu/Newell/. Newell’s Nachlass.

Card, Stuart K., Thomas P. Moran, and Allen Newell. The Psychology of Human-Computer Interaction. Hillsdale, N.J.: LEA, 1983.

Feigenbaum, Edward A., and J. Feldman, eds. Computers and Thought.  New York: McGraw-Hill, 1963.  Reprints some of Newell, Shaw, and Simon’s early AI papers.

Unified Theories of Cognition. Cambridge, MA: Cambridge University Press, 1990.

“Précis of Unified Theories of Cognition.” Behavioral and Brain Sciences 15 (1992): 425-492.  With commentaries by many cognitive scientists and a response by Newell.

Newell, Allen, Hugh S. Kelly, Fred M. Tonge, Edward A. Feigenbaum, Bert F. Green, Jr., and George H. Mealy. Information Processing Language-V Manual, Second Edition. Englewood Cliffs, N.J.: Prentice-Hall, 1964.

Newell, Allen, and Herbert Simon. Human Problem Solving.  Englewood Cliffs, N.J.: Prentice-Hall, 1972.

Rosenbloom, Paul S., John E. Laird, and Allen Newell, eds. The Soar Papers: Research on Integrated Intelligence, vol. 2. Cambridge, MA: MIT Press, 1993.

Siewiorek, Daniel P., C. Gordon Bell, and Allen Newell. Computer Structures: Principles and Examples. New York: McGraw-Hill, 1982.

 

Works About Newell:

Boden, Margaret. Mind as Machine: A History of Cognitive Science. Oxford: Oxford University Press, 2006.  Devotes many pages to Newell’s work and its historical role.

Laird, John E., and Paul S. Rosenbloom. “The Research of Allen Newell.” AI Magazine 13.4 (1992): 17-45.

Michon, John, and Aladin Akyurek, eds. Soar: A Cognitive Architecture in Perspective. Norwell, MA: Kluwer Academic, 1992.

Simon, Herbert A. “Allen Newell: 1927-1992.” IEEE Annals of the History of Computing 20.2 (1998): 63-76.

Steier, David, and Tom M. Mitchell, eds. Mind Matters: A Tribute to Allen Newell. Mahwah, N.J.: LEA, 1996.