Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Operational sequencing of two halting Word-RAM runs

Proved
DirKECC1549.Main.program_sequence_runs

by parclytaxel · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

computabilityword-ram

Let ppp and qqq be fixed multiplication Word-RAM programs. There exists a fixed multiplication Word-RAM program sss that sequences their halting executions at every positive word width, on arbitrary initial memory.

More precisely, suppose running ppp from memory MMM for interpreter fuel f1f_1f1​ produces a halted state S1S_1S1​, and running qqq from S1S_1S1​'s memory for fuel f2f_2f2​ produces a halted state S2S_2S2​. Then there is interpreter fuel fff for which running sss from MMM produces a halted state SSS with

S.mem=S2.mem,S.ticks≤S1.ticks+S2.ticks.S.\mathrm{mem}=S_2.\mathrm{mem},\qquad S.\mathrm{ticks}\le S_1.\mathrm{ticks}+S_2.\mathrm{ticks}.S.mem=S2​.mem,S.ticks≤S1​.ticks+S2​.ticks.

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 sss depends only on ppp and qqq, 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.

Preamble
import Definitions.Def_DirKECC1549_Main_Machine
set_option autoImplicit false
open WordRAM
Formal statement
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
Source
Derived operational lemma for DirKECC1549.Main.hitting_program_compose, https://prove2.me/theorems/d459a263-532a-44b0-b0ce-1eee26cd293c; based on runFrom in Definitions.Def_DirKECC1549_Main_Machine and execute, step, run in Definitions.Def_WordRAMEquivalence_Foundation1. The parent is the implementation obligation for Section 3.2.1, Algorithm 2 and Lemma 2, pp. 13–14, of STOC 2027 submission #1549.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me