Computer Science as Empirical Inquiry: Symbols and Search
Authors: Allen Newell, Herbert A. Simon
Year: 1976 | Communications of the ACM (ACM Turing Award Lecture)
Source: newell-1976-computer-science-as-empirical-inquiry
What it is
Newell and Simon’s 1975 ACM Turing Award lecture — the theoretical manifesto of symbolic AI. They proposed the Physical Symbol System Hypothesis: that symbol manipulation is both necessary and sufficient for general intelligent action. This is the strongest possible claim for symbolism: not just that symbol-processing systems can be intelligent, but that any intelligence must be a symbol system.
Physical Symbol System: what it means
A physical symbol system has:
- Symbols — physical patterns (voltage states, ink marks, neural firing patterns) that can be created, copied, modified, destroyed
- Expressions — structures built from symbols (lists, trees, sequences)
- Processes — operations that take expressions as input, produce expressions as output
- Designation — the crucial property: a symbol can refer to (stand for) any expression in the system
The designation property is what gives symbols their power. A symbol isn’t just a pattern — it can point to other patterns, allowing the system to represent arbitrary abstract structures.
Examples of physical symbol systems: digital computers (unambiguously), human brains (hypothesized).
The Hypothesis
“A physical symbol system has the necessary and sufficient means for general intelligent action.”
Sufficient
A PSS can exhibit general intelligence. Evidence: the Logic Theorist (1956) proved 38 of the first 52 theorems in Principia Mathematica. General Problem Solver (GPS, 1957) solved diverse problems using means-ends analysis. These programs are symbol systems, and they perform tasks that required human intelligence.
Necessary
Any system that exhibits general intelligence must be a physical symbol system. This is the stronger, more contested claim. It implies:
- Continuous/analog systems cannot be generally intelligent without being interpretable as symbol systems
- Purely statistical systems (neural networks, for example) would need to be interpreted as implicit symbol systems to count as intelligent
The hypothesis is empirical — it’s a scientific conjecture, not a theorem. It makes falsifiable predictions.
Heuristic Search
Given a symbol system, how does intelligent behavior work? The paper’s answer: heuristic search.
Problem = initial state + goal state + operators
Intelligence = searching the problem space from initial to goal
guided by heuristics that prune unpromising paths
Key insight: problem spaces are too large to search exhaustively, so intelligence requires knowledge in the form of heuristics — rules that say which moves are likely to be useful.
Means-ends analysis (the GPS heuristic): at each step, identify the biggest difference between current state and goal, and select the operator most likely to reduce that difference.
Why this was the theoretical foundation of symbolic AI
Before this paper, AI programs existed but there was no unifying theory of why they worked or what intelligence was. Newell and Simon provided:
- A definition of the substrate of intelligence (symbol systems)
- A claim about necessity (you can’t do it without symbols)
- A mechanism (heuristic search)
This gave symbolic AI a research program: build better symbol systems with better heuristics for searching larger problem spaces.
The challenge from connectionism
The Physical Symbol System Hypothesis predicts that neural networks, which don’t explicitly manipulate symbols, cannot be genuinely intelligent — or if they are, they must be interpretable as symbol systems.
The deep learning era challenged this directly: neural networks achieved general-purpose language understanding, visual reasoning, and planning without explicit symbol manipulation. Whether this falsifies the PSSH or merely shows that neural networks implicitly implement symbol systems remains debated.
The two AI traditions in one diagram
Dartmouth 1955 ──→ McCarthy 1958 ──→ Robinson 1965 ──→ Expert Systems 1970s
(symbolic AI) (logic) (resolution) (knowledge bases)
↑
Newell & Simon 1976: theoretical foundation of this line ──────┘
Hebb 1949 ──→ Rosenblatt 1958 ──→ Rumelhart 1986 ──→ LeCun 1998 ──→ Vaswani 2017
(connectionism) (perceptron) (backprop) (CNN) (Transformer)
See also
- mccarthy-1955-a-proposal-for-the-dartmouth — The Dartmouth program whose theory this provides
- mccarthy-1958-programs-with-common-sense — Concrete symbolic AI system (Advice Taker)
- rosenblatt-1958-the-perceptron-a-probabilistic-model — The connectionist alternative, resurgent after 2012