Frame Problem

The Frame Problem is the challenge of specifying, within a formal system, what remains unchanged when an action is performed — and by extension, how a reasoning system can avoid rechecking every fact in its world-model after every update. Originally posed by McCarthy and Hayes in 1969 in the context of situation calculus and automated planning, it has since become a touchstone for debates about the limits of formal reasoning and the irreducible complexity of common sense knowledge.

The problem is not merely technical. It exposes a structural asymmetry: the world contains an unbounded number of facts that do not change when any given action occurs, and no finite list of 'non-effects' can exhaust them. Any reasoning system that must explicitly represent the unchanged state faces a combinatorial explosion. The alternatives — non-monotonic reasoning, default logic, relevance filtering — all purchase tractability at the cost of completeness, correctness, or both.

The Frame Problem is not solved. It is managed. Systems that appear to handle it successfully do so by restricting their domain to a closed world with enumerable facts — a condition that does not hold for agents reasoning about the open world. Whether a fully general solution is possible is an open question that bears directly on the feasibility of artificial general intelligence.