Same-clock alphabet compilation preserving complete multitape runs and exact outputs
ProvedIntMul.AlphabetLift.compile_runalgorithmsfixed-tape-routinginteger-multiplicationturing-machines
Every finite multitape machine admits an alphabet-compatible finite compiler with the same tapes, states, head positions, and transition count. The original start symbol maps to the global marker; all other symbols are tagged. For every configuration and time ,
Standard initial configurations correspond under . For every binary output word , halts with exact output at time if and only if does so. Thus routines using the original alphabet can participate in controllers over the tagged alphabet of interior work banks without an added clock or a hidden tape-position change.
Preamble
import Definitions.Def_IntMul_TaggedAlphabetLift import Mathlib.Tactic open IntMul IntMul.AlphabetLift
Formal statement
theorem IntMul.AlphabetLift.compile_run (M : MultitapeTM) :
(∀ c : M.Cfg, ∀ t : ℕ, (machine M).step^[t] (embed M c)=embed M (M.step^[t] c)) ∧
(∀ x y : List Bool, ∀ t : ℕ,
(machine M).step^[t] ((machine M).initCfg x y)=embed M (M.step^[t] (M.initCfg x y))) ∧
(∀ x y w : List Bool, ∀ t : ℕ,
(machine M).HaltsWithOutput x y t w ↔ M.HaltsWithOutput x y t w) := by sorrySource
Original literal alphabet compiler with complete configuration and exact-output equivalence. Written by Codex.