Endogenous Interpretation
In the authors' words
We propose endogenous interpretation: program, interpreter, machine, and derived execution language are not disjoint semantic objects but different parameterizations of one executable state-transition relation. Each realization carries an implicit constraint bias, the structural restrictions imposed by its instruction basis, state encoding, control transfers, and finite substrate. From this viewpoint the "semantic gap" metaphor is misleading for operational semantics: a semantics-preserving transformation cannot remove the computation required for execution; it redistributes it over another state space and transition granularity (semantic diffusion). Reverse engineering is then the recovery of a lower-complexity semantic contraction. We give a first quantitative instance. For finite-state realizations observed up to bisimulation, the contraction is canonical and computable in almost-linear time, yielding an abstraction-independent diffusion ratio; for deterministic realizations this extends to trace equivalence. For nondeterministic realizations observed up to traces, minimal contraction is
Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 15 pages. Working paper; comments welcome. Sections 6-8 contain the formal results; Section 7.5 describes proposed experiments not yet carried out