Operational sequencing of two halting Word-RAM runs
ProvedDirKECC1549.Main.program_sequence_runsLet and be fixed multiplication Word-RAM programs. There exists a fixed multiplication Word-RAM program that sequences their halting executions at every positive word width, on arbitrary initial memory.
More precisely, suppose running from memory for interpreter fuel produces a halted state , and running from 's memory for fuel produces a halted state . Then there is interpreter fuel for which running from produces a halted state with
Each component run starts with program counter and tick count zero. No condition is imposed on uninitialized memory, instruction literals, or jump targets beyond the two successful-halting hypotheses. The program depends only on and , not on the word width, memory, or fuel.
This is the operational sequencing obligation needed to compose subroutine contracts, independent of graph encodings and polynomial capacity bounds.
import Definitions.Def_DirKECC1549_Main_Machine set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem program_sequence_runs
(p q : Complexity.Program .multiplication) :
∃ code : Complexity.Program .multiplication,
∀ (w : Width) (mem : Memory w) (f₁ f₂ : ℕ),
(runFrom p w mem f₁).halted = true →
(runFrom q w (runFrom p w mem f₁).mem f₂).halted = true →
∃ fuel : ℕ,
(runFrom code w mem fuel).halted = true ∧
(runFrom code w mem fuel).ticks ≤
(runFrom p w mem f₁).ticks +
(runFrom q w (runFrom p w mem f₁).mem f₂).ticks ∧
(runFrom code w mem fuel).mem =
(runFrom q w (runFrom p w mem f₁).mem f₂).mem := by sorry
end DirKECC1549.Main