Transition Calculus: A Theory of Self-Describing Learnable Transition Systems

Turing characterized computability. Shannon characterized information. The structural conditions under which both properties coexist with symbolic readability in a single primitive have not been formally characterized. We provide that characterization. We define the Self-Describing Transition System (SDTS) — a transition system whose vocabulary is neither fixed nor externally specified but is discovered from data and extended from within by a reserved meta-transition. We prove three central results: the Readability Theorem (any SDTS computation is losslessly recoverable from its label sequence); the Learnability Theorem (the SDTS vocabulary is PAC-learnable with explicit sample complexity m = O((k log(|V|/k) + d log(1/ε) + log(1/δ)) / ε²)); and the Frozen Decoder Property (vocabulary extension via DEFINE never modifies the base execution substrate). We prove the Minimality Theorem: no proper subset of the four defining properties — named transitions, discrete vocabulary, admissible learning mechanism, and self-extension — simultaneously guarantees all three structural invariants, where those invariants are defined independently of the SDTS construction. We introduce the Transition Calculus governing how named transitions compose, extend, and interact. We state the Complexity Conjecture: connecting the minimum SDTS description length to Kolmogorov complexity, building on the invariance theorem to characterize the SDTSspecific encoding cost. We show that existing computational theories — Turing machines, Shannon entropy, symbolic AI, and continuous neural networks — are each partial instantiations of this primitive, and that the long-standing divide between neural and symbolic computation is not a fundamental dichotomy but a consequence of implementing only a subset of the primitive's properties. The theory makes testable predictions about biological neural systems, the structure of learned representations, and the computational complexity of classification problems. Keywords: transition systems, symbolic computation, computational learning theory, neurosymbolic integration, Kolmogorov complexity, minimum description length, selfdescribing systems, interpretability