Source Summary: Newell & Simon 1976 — Physical Symbol Systems
Full title: Computer Science as Empirical Inquiry: Symbols and Search
Authors: Allen Newell, Herbert A. Simon
Affiliation: Carnegie Mellon University
Venue: Communications of the ACM, 19(3), pp. 113–126 (1976) — ACM Turing Award Lecture
PDF: papers/newell-1976-computer-science-as-empirical-inquiry.pdf
Note: PDF is scanned; content from the paper itself.
Contributions
- Physical Symbol System Hypothesis — the central thesis of symbolic AI: “A physical symbol system has the necessary and sufficient means for general intelligent action.”
- Definition of symbol systems — a formal framework for what it means to manipulate symbols, applicable to both computers and human minds.
- Heuristic search as the mechanism of intelligence — intelligent behavior = searching a space of symbolic expressions guided by heuristics.
Physical Symbol System: Definition
A physical symbol system consists of:
- Symbols: physical patterns (voltage states, ink marks, neural patterns) that can be created, copied, destroyed
- Expressions: structures built from symbols (lists, trees, graphs)
- Processes: operations that take expressions as input and produce expressions as output — including reading, writing, branching, and designating (a symbol can point to another expression)
The crucial property: designation — a symbol can refer to (stand for) any expression in the system. This gives symbols their semantic power.
Examples: a digital computer, the human brain (hypothesized).
The Hypothesis
“A physical symbol system has the necessary and sufficient means for general intelligent action.”
Sufficient: a PSS can be organized to exhibit general intelligent action — proven by the existence of programs (Logic Theorist, GPS) that solve problems requiring intelligence.
Necessary: any system exhibiting general intelligence must be a PSS — a stronger empirical claim. If true, intelligence cannot exist without symbol manipulation.
The hypothesis is explicitly empirical, not logical — it cannot be proved from first principles, only supported or refuted by evidence.
Heuristic Search
Given the symbol system, how does intelligence work? The paper’s answer: heuristic search.
Problem solving = searching through a space of symbolic expressions (problem space) from initial state to goal state, guided by:
- Operators: rules for transforming expressions
- Heuristics: knowledge that prunes the search space
Evidence: the Logic Theorist (1956) proved theorems from Principia Mathematica by heuristic search. The General Problem Solver (GPS, 1957) used means-ends analysis to solve diverse problems.
Historical context
This was Newell and Simon’s 1975 ACM Turing Award lecture. By 1976, they had:
- Built Logic Theorist (1956) — first AI program, proved 38 theorems from PM
- Built GPS (1957) — General Problem Solver, means-ends analysis
- Published Human Problem Solving (1972) — unified theory of human and machine cognition
The Physical Symbol System Hypothesis was the theoretical unification of this work.
Key References
- Newell & Simon 1956 — Logic Theorist
- Newell, Shaw & Simon 1957 — General Problem Solver
- Turing 1950 — Computing Machinery and Intelligence
- McCarthy 1958 — Programs with Common Sense