The Synthesis of Digital Machines with Provable Epistemic Properties

Reference: Rosenschein, S.J. & Kaelbling, L.P. (1986). Theoretical Aspects of Reasoning about Knowledge: Proceedings of the 1986 Conference (J.Y. Halpern, ed.), Morgan Kaufmann, pp. 83–98. Source file: rosenschein-kaelbling-synthesis-digital-machines.pdf. URL

Summary

Rosenschein and Kaelbling introduce the situated-automata approach to knowledge: rather than treating K(x, phi) as “machine x stores a syntactic representation of phi in its knowledge base”, they define it in terms of a correlation between the state of the machine and the state of its environment. A machine “knows” phi iff phi holds in every environment-state consistent with the machine’s internal state. Under this definition the S5 axioms of epistemic logic fall out as theorems about well-designed embedded systems — without any symbolic storage of formulas.

The paper extends earlier situated-automata work to compositional hardware: synchronous digital machines are analysed by treating their gates and delay elements as agents in a multi-agent system and reasoning about information flow among them. The authors introduce Rex, a language for recursively computing machine descriptions that lets designers build machines with provable epistemic properties from the gate level up. This is the technical foundation for “knowledge as situatedness” that underpins reactive agent architectures.

Key Ideas

Situated-automata semantics: knowledge = correlation between machine state and environment state, not syntactic storage.
S5 axioms (truth, consequential closure, positive and negative introspection) provable for embedded systems under this definition.
Compositional reasoning: gates and delays modelled as agents; knowledge of the whole follows from information flow among components.
Rex: a hierarchical specification language that compiles to digital machines with guaranteed epistemic properties.
Provides a bridge between epistemic logic, control theory, and reactive robotics.

Connections

Conceptual Contribution

Claim: Knowledge in an embedded agent can be defined by state-environment correlation, so epistemic properties can be compiled into hardware rather than reasoned about at runtime.
Mechanism: Possible-worlds semantics where a machine’s internal state partitions environment states; Rex language synthesises circuits whose state partitions provably realise specified knowledge predicates.
Concepts introduced/used: Situated Automata, Correlational Knowledge, Rex Language, Epistemic S5, Embedded Agent.
Stance: foundational/formal; engineering-oriented counterpoint to symbolic AI.
Relates to: Shoham’s Agent-Oriented Programming cites this work as a key alternative route to agenthood: where AOP implements mental state as explicit data structures interpreted at runtime, Rosenschein & Kaelbling show mental state can be compiled away while preserving the same logical semantics. Shoham’s discussion of “natural vs artificial automata” and of Reactive vs Deliberative Agents directly engages with this programme.

Tags

#situated-automata #epistemic-logic #reactive-agents #foundational #compilation #knowledge

Backlinks

Reactive vs Deliberative Agents

A classical dichotomy in agent architecture: reactive agents (Brooks, subsumption) respond to percepts via hardwired stimulus-response rules without explicit world models; deliberative agents (BDI, planning) maintain symbolic representations and reason over them before acting. Hybrid architectures combine a reactive lower layer with a deliberative upper layer.

Summary

Shoham introduces Agent-Oriented Programming (AOP) as a specialization of object-oriented programming in which the state of each module — now called an agent — is a mental state composed of beliefs, capabilities, decisions/choices, commitments, and obligations. Interpretation of these components is formally grounded in an extension of standard epistemic logics that adds temporality, obligation, decision, and capability operators.

Agents communicate via speech-act-inspired primitives (inform, request, offer, promise, decline, etc.), constrained by rules such as honesty and consistency. The paper defines a class of agent interpreters and presents AGENT-0, a concrete implemented language whose semantics is tied to the mental-state logic. Shoham also discusses “agentification” — converting arbitrary devices into AOP-programmable agents — and situates AOP against BDI architectures, speech act theory, and McCarthy’s Elephant2000.

Conceptual Contribution

Claim: Programming can be fruitfully specialised to an “agent” paradigm in which module state is a formally specified mental state and inter-module communication is a speech act constrained by rational/ethical rules.

Mechanism: Shoham extends standard modal-epistemic logic with temporal, obligation, decision and capability operators, defines the mental-state components of an agent (belief, capability, commitment, choice, obligation), then specifies a generic agent interpreter cycle (update mental state, execute commitments, handle incoming messages) and instantiates it in AGENT-0, whose programs are condition-action rules over mental state and whose messages are typed INFORM/REQUEST/UNREQUEST primitives.

Concepts introduced/used: Agent-Oriented Programming, Mental State, Commitment, AGENT-0, Speech Act Theory, Agentification, BDI, Honesty Constraint

Stance: foundational

Relates to: Establishes the mentalistic ACL stance later criticised by Agent Communication Languages - Rethinking the Principles and surveyed by Intelligent Agents Theory and Practice; AGENT-0’s speech-act primitives anticipate KQML as an Agent Communication Language and FIPA-ACL; the mental-state architecture is reused in An Interaction-oriented Agent Framework for Open Environments.