Introduction
Traditional artificial intelligence logic often assumes "logical omniscience," the premise that an agent instantly knows all logical consequences of its current knowledge. However, human reasoning is a temporal process where deductions take time. This paper introduces step-logic, a formalism that treats reasoning as an incremental activity occurring in real-time. By applying this to the classic Three-Wise-Men puzzle, the author demonstrates how agents can use the passage of time—specifically the silence of others—as a critical logical input to solve complex epistemic problems.
Methodology: The $SL_5$ Theory
The core of the approach is Step-logic, specifically an $SL_5$ theory. Unlike standard static logics, step-logic is discrete and incremental. At each step $i$, the agent applies specific inference rules to the beliefs held at step $i-1$. This allows for temporal awareness through a successor function $s(i)$ and predicates such as $K_j(i, \alpha)$, representing that agent $j$ knows $\alpha$ at step $i$.
A critical component of this system is Rule 6, which enables negative introspection. This rule allows an agent to realize that if a certain announcement (utterance) hasn't been made by a specific step, it implies that other agents have not yet reached that conclusion. This captures the essence of reasoning in time rather than just about time.
Key Insights: Silence as Information
In the Three-Wise-Men problem, the solution hinges on the fact that other participants haven't spoken. Step-logic formalizes this "silence as information." If Wise Man #2 were to know his hat color, he would have announced it by a certain step $n$. His continued silence at step $n+1$ provides Wise Man #1 with the evidence needed to update his own beliefs. This approach models the reasoning from the perspective of the agent, giving it the power to reason about its own mental timeline and the perceived timelines of others.
Results: Solving the Puzzle
The paper provides a complete formal trace of Wise Man #1’s reasoning process across 17 discrete steps.
Initially, the agent starts with axioms regarding the game's rules and the capabilities of the other men. Between steps 2 and 11, the agent performs internal deductions regarding what others might conclude under different conditions. By step 17, after accounting for the observed silence of the other two men, Wise Man #1 successfully concludes, "My card is white!" ($W_1$). The author notes that while a two-man version is simpler, the three-man version requires modeling the continuous reasoning of others rather than just initial states.
Limitations and Future Work
While effective for this benchmark, step-logic faces challenges in computational complexity. Managing which conclusions are "interesting" enough to pursue at each step remains a significant hurdle. Furthermore, while this specific puzzle is monotonic, more complex commonsense reasoning would require mechanisms for the retraction of beliefs (nonmonotonicity) to handle new information that contradicts old conclusions. Future research will focus on scaling these logical structures to more complex social and temporal environments.
Summary updated