— Ch. 1 · Origins And History —
Situation calculus.
~4 min read · Ch. 1 of 7
John McCarthy introduced the situation calculus in 1963 to solve a specific problem in artificial intelligence. He needed a way for machines to reason about changing worlds without getting lost in infinite possibilities. The field evolved significantly over three decades until Ray Reiter published his definitive formulation in 1991. This modern version redefined what a situation actually meant within the logic system. McCarthy originally viewed situations as complete states of the universe at an instant, but Reiter changed that definition entirely. His work shifted the focus from static snapshots to dynamic histories of actions. The evolution continued with McCarthy releasing a revised version in 1986 that incorporated functional fluents. These changes laid the groundwork for automated reasoning systems used today.
Core Logical Elements
A domain in this formalism relies on three fundamental sorts: actions, situations, and objects. Variables of each sort can be quantified independently to build complex logical statements. Fluents serve as the bridge between these elements by describing properties that change over time. In the standard robot world example, a fluent named carries indicates whether the robot holds a specific object. Another fluent called location returns the coordinate point where the robot currently stands. Actions like move or pick up function as terms that modify these state descriptions. The predicate executable determines if a given action can legally occur in a current situation. A special constant S0 denotes the initial situation before any actions have been performed. Every new situation results from applying an action function to a previous situation and an action term.The Frame Problem Solution
Early versions of the calculus struggled to derive non-effects of actions without explicit axioms. Designers had to write frame axioms stating that every unaffected property remains unchanged after an operation. This approach became unmanageable as the number of possible interactions grew exponentially. Ray Reiter solved this issue with successor state axioms in 1991. These axioms allow the system to deduce all changes from a single formula per fluent. The formula states that a fluent is true in a successor situation if it was made true by the action or if it was already true and not negated by the action. This eliminates the need for hundreds of separate frame axioms. The logic now handles inertia automatically through the structure of the axiom itself. Designers only need to specify how fluents change rather than how they stay the same.