Introduction
While the standard modal logic S5 is often considered the "gold standard" for modeling knowledge, it operates in a vacuum of abstraction. In the realm of AI and distributed systems, physical constraints—such as a machine’s memory capacity or its interaction patterns with the environment—can render certain logically consistent states of knowledge physically impossible. This paper bridges the gap between abstract logic and the practical epistemic properties of machines through a new framework and specific axioms.
The Gap Between Logic and Physics
In distributed computing, we often say "Robot A knows the door is locked." Traditionally, this is modeled using S5 modal logic, which assumes knowledge follows specific rules (e.g., if you know something, it must be true). However, S5 doesn't account for the "physics" of the system. For instance, if a robot is programmed with cumulative knowledge (it never forgets) and its transitions are independent of the environment, are there certain "states of mind" it simply cannot reach? The authors investigate whether every Kripke structure—the mathematical foundation of S5—actually corresponds to a state a real machine can inhabit.
The Situated-Automata Approach
The authors move away from purely symbolic logic to a situated-automata approach, defining a system as a set of "runs" (sequences of global states over time). This model relies on several key components:
- Global States: A combination of the environment's state and the local states of all components.
- Indistinguishability: A process "knows" a fact if that fact is true in every global state where the process maintains the same local state.
- System Parameters: The authors vary three critical assumptions:
- Cumulative Knowledge: Does the machine have unbounded memory?
- Environment Interaction: Does the environment determine the initial state?
- Transition Independence: Do internal changes depend on the external world?
Key Insights: The Pasting Condition and Paradoxes
A central contribution is the "pasting condition." If a system is cumulative and environment-independent, its possible states of knowledge must be "pastable" together. If a state fails this condition, a machine under those constraints can never reach it, even if it is logically consistent in S5.
To illustrate this, the authors present the Alice and Bob Paradox. In a scenario with two robots, a specific state of knowledge—where Alice knows that either Bob knows a fact or the fact is false—is shown to be unattainable if the robots are "honest" and have specific memory constraints.
Furthermore, the paper distinguishes between Implicit Knowledge ($I$) and explicit knowledge. Implicit knowledge represents what a group of machines could know if they pooled their information. In systems where the initial state uniquely determines the environment, a new axiom emerges: $\phi \implies I\phi$ (if something is true, it is implicitly known by the system).
Results and Axiomatization
The authors derive new, precise axiomatizations that extend beyond standard S5:
- Theorem 4.3: Provides a sound and complete axiomatization for "ideal" systems (cumulative, environment-determined, and independent). This system, $ML_n$, introduces a "rather mysterious" axiom ($A6$) to handle distributed knowledge.
- Theorem 4.4: Proves that S5 is only "incomplete" when all three physical constraints are met simultaneously. Dropping even one constraint causes the extra restrictions to vanish, making S5 a complete description again.
- Theorem 4.7: Establishes that for systems where process states uniquely determine the environment, S5 remains sound and complete for simple knowledge, but requires the $A7$ axiom for implicit knowledge.
Conclusion and Future Directions
This work highlights the fragility of completeness in epistemic logic when applied to physical systems. While the current analysis assumes static environments and discrete time, it sets the stage for future research into Common Knowledge and Temporal Modalities (how knowledge evolves over time). By grounding logic in the physical realities of machines, the authors provide a more robust framework for reasoning about what machines can truly "know."
Summary updated