Substrate-Independent Computation: Existence and Constructivity of Computational Functions in Chaotic Media

This paper establishes the mathematical and algorithmic foundations of Substrate-Independent Computation (SIC), proving that computation is independent of the design of its physical substrate. An undesigned, chaotic physical system mathematically contains every finite computational function. The primary contribution is the Textbook Transfer Theorem (Theorem 8): functionality mined on one substrate can be transferred to any new substrate via a textbook, at the cost of only n calibration shots and an n-entry renaming table, without re-mining. This breaks the "one-off" limitation of prior experimental demonstrations. The remaining results organize the landscape around this mechanism: 1. Existence layer: Lookup-table realizations are trivial.2. Capacity layer: Two capacity theorems give necessary and sufficient conditions for exact linear-readout realization (n ≤ min(d, D) and n ≤ min(D, d^2)).3. Phase-only constraint: Capacity drops to d^2 - d + 1. Historical Analogy: Prior demonstrations carved computational functions into individual stone tablets; this work studies movable type — the semantic layer (textbooks, letters) as type that can be rearranged and reused across substrates. They carved stones; we cast type. When the road of precision manufacturing ends, chaos remains there, waiting to be educated.