Source Summary: McCarthy & Hayes 1969 — Some Philosophical Problems from the Standpoint of AI
Full title: Some Philosophical Problems from the Standpoint of Artificial Intelligence
Authors: John McCarthy, Patrick J. Hayes
Affiliation: Stanford University
Venue: Machine Intelligence 4 (Meltzer & Michie, eds.), Edinburgh University Press, pp. 463–502 (1969)
PDF: papers/mccarthy-1969-some-philosophical-problems-from-the.pdf
Contributions
- Situation calculus — a formal logical framework for representing the world as a sequence of situations, actions, and their effects; the foundation of AI planning and reasoning about action.
- The frame problem — identified and named the problem of representing what doesn’t change when an action occurs; one of the central unsolved problems of symbolic AI.
- Epistemological vs. heuristic adequacy — a distinction between representing knowledge correctly (epistemological) and using it efficiently (heuristic) — the two goals can conflict.
Situation Calculus
The paper introduces a formal language for reasoning about change:
- Situation: the complete state of the world at a point in time (S₀, S₁, S₂, …)
- Fluent: a property that can change over time (e.g.,
At(robot, room),Holding(robot, block)) - Action: an operation that transforms one situation into another
- Result function:
Result(a, s)= the situation that results from performing actionain situations
Example axioms:
At(robot, room1, S0) ← robot is in room1 at S0
Result(move(room1, room2), S0) = S1 ← moving produces S1
At(robot, room2, S1) ← robot is in room2 at S1
This formalism lets an AI system reason about plans: what sequence of actions will bring about a desired situation?
The Frame Problem
The key challenge the paper identifies: when an action is taken, most facts about the world remain unchanged. But in a logical representation, you can’t assume facts persist — you have to assert them.
Example: after move(room1, room2):
- The robot’s location changes
- But the color of the robot, the location of every other object, the temperature of the room… all remain the same
In predicate calculus, you’d need to assert every unchanged fact — an infinite list. This is the frame problem: how to represent persistence compactly and correctly.
The paper proposes frame axioms — explicit statements like “moving the robot doesn’t change the locations of blocks” — but acknowledges this is unsatisfactory: the number of frame axioms grows as the product of (actions × fluents).
Adequacy Criteria for Knowledge Representations
The paper introduces a useful framework for evaluating knowledge representations:
- Metaphysically adequate: the representation could in principle describe the world correctly
- Epistemologically adequate: the representation can express facts that agents actually have — practical, not just theoretically possible
- Heuristically adequate: reasoning in this representation is computationally feasible
A representation can be metaphysically adequate (e.g., full predicate calculus) but heuristically inadequate (inference is too slow). Practical AI requires all three.
Impact
Situation calculus and the frame problem defined the research agenda of symbolic AI planning for the following two decades:
- STRIPS (1971) — Fikes & Nilsson’s planning system used situation calculus + frame axioms
- Non-monotonic reasoning (1980s) — McCarthy’s circumscription, Reiter’s default logic, etc., all attempted to solve the frame problem via non-monotonic inference
- Event calculus (1986) — Kowalski & Sergot’s alternative to situation calculus
The frame problem was never fully solved in symbolic AI. Neural networks sidestep it by learning what typically persists from data — but at the cost of not being able to explain why things persist.
Key References
- McCarthy 1958 — Programs with Common Sense (the earlier, less formal version of these ideas)
- Fikes & Nilsson 1971 — STRIPS (direct application of situation calculus)
- McCarthy 1980 — Circumscription (attempted solution to the frame problem)