AI/ML Wiki

mccarthy-1969-some-philosophical-problems-from-the

4 min read

Some Philosophical Problems from the Standpoint of Artificial Intelligence

Authors: John McCarthy, Patrick J. Hayes
Year: 1969 | Machine Intelligence 4
Source: mccarthy-1969-some-philosophical-problems-from-the

What it is

This paper introduced situation calculus — a formal logical language for reasoning about actions, change, and the world over time. More consequentially, it identified and named the frame problem: the challenge of representing what doesn’t change when an action occurs. The frame problem became symbolic AI’s central unsolved challenge for two decades, and its difficulty is one reason neural networks eventually displaced logic-based AI.

Situation calculus

The paper builds a formal ontology for reasoning about a changing world:

  • Situation S: the complete state of the world at an instant
  • Fluent F(s): a property that varies with the situation (e.g., At(robot, room1, s))
  • Action A: an operation that transitions between situations
  • Result: Result(a, s) = the situation that results from doing action a in situation s

Example of reasoning about a plan:

At(robot, room1, S₀)                      ← initial fact
Holding(robot, nil, S₀)                   ← initial fact

Result(pickup(block), S₀) = S₁            ← pickup transitions to S₁
Holding(robot, block, S₁)                 ← effect of pickup
At(robot, room1, S₁)                      ← unchanged (frame axiom needed!)

Result(move(room1, room2), S₁) = S₂       ← move transitions to S₂
At(robot, room2, S₂)                      ← effect of move

This formalism lets a reasoning system construct proofs that a sequence of actions achieves a goal — the basis of AI planning.

The frame problem

The critical challenge lurking in the example above: after pickup(block), the robot’s location At(robot, room1) is unchanged. But in classical logic, you cannot assume facts persist — you must explicitly assert them.

For a world with N fluents and M actions, you need up to N×M frame axioms:

"Picking up a block doesn't change the robot's location"
"Picking up a block doesn't change the block's color"
"Picking up a block doesn't change the temperature of the room"
...

This explosion of assertions is the frame problem. McCarthy and Hayes proposed frame axioms as a workaround, but acknowledged it was unsatisfactory — the axioms are tedious, error-prone, and don’t scale.

Why the frame problem matters

The frame problem is not just an engineering inconvenience. It reveals something deep about the mismatch between logic and common sense:

In logic: everything must be explicitly stated. Silence = unknown.

In common sense: most things persist by default. Change is the exception, not the rule.

Closing this gap required departing from classical logic:

  • Non-monotonic reasoning (1980s): default assumptions that can be overridden
  • McCarthy’s circumscription (1980): minimize the extension of predicates not mentioned in an action’s effects
  • Reiter’s default logic (1980): formal rules for reasoning under incomplete information
  • Event calculus (Kowalski 1986): alternative temporal logic that handles persistence differently

None of these fully solved the frame problem. Neural networks sidestepped it entirely — they learn what typically changes from data, without ever explicitly representing frame axioms.

Epistemological vs. heuristic adequacy

The paper draws a key distinction that became central to knowledge representation:

Epistemologically adequate: the representation can correctly express any fact an agent might have.

Heuristically adequate: reasoning in this representation is computationally feasible in practice.

A full predicate calculus is epistemologically adequate — you can express anything. But it’s heuristically inadequate for many tasks: inference is semi-decidable, and relevant conclusions may require exponentially long proofs.

This tension — expressiveness vs. tractability — runs through all of symbolic AI and is why practical expert systems use restricted logics (Horn clauses, description logics) rather than full first-order logic.

Historical impact

McCarthy & Hayes 1969 (frame problem)
        ↓
STRIPS 1971 (Fikes & Nilsson) — first practical planner; used limited frame axioms
        ↓
Non-monotonic logics 1980s — attempted formal solutions
        ↓
"Symbol grounding problem" (Harnad 1990) — related: symbols don't connect to world
        ↓
Neural networks learn persistence implicitly (1986–present) — practical sidestep
        ↓
World models (LeCun 2022) — explicit temporal models of what persists and changes

See also

Graph View

Backlinks