Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite tape simulation with the explicit interpreter clock

Proved
Lax759944Proofs.TapeRamGenericTime.genericTime_of_lowering_finite_explicit

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmscomputational-complexitylinear-programming

Suppose a lowering sends every finite word-RAM program to the legacy RAM and simulates ttt steps at width vvv within 18t+6(∣x∣+1)+2618t+6(|x|+1)+2618t+6(∣x∣+1)+26 steps at width v+1v+1v+1, whenever the encoded input and its length satisfy the stated width guards. Suppose also that the binary encoding length b(x)b(x)b(x) is at least ∣x∣|x|∣x∣. For every program ppp and natural-coefficient width polynomial WWW, there is a single tape machine with finite alphabets and a width-overhead polynomial W′≥WW'\ge WW′≥W. Every run of ppp on ∣x∣::x|x|::x∣x∣::x producing yyy at width W′(b(x))W'(b(x))W′(b(x)) is simulated on the binary word encodings, provided ∣x∣::x|x|::x∣x∣::x and yyy fit width W(b(x))W(b(x))W(b(x)).

Its actual tape execution is bounded by

Pcompile⁡(lower⁡(p)), W+X+7, X(100(b(x)+t+1)),P_{\operatorname{compile}(\operatorname{lower}(p)),\,W+X+7,\,X}\bigl(100(b(x)+t+1)\bigr),Pcompile(lower(p)),W+X+7,X​(100(b(x)+t+1)),

where PPP is the explicit interpreter time polynomial from the published operational definitions. Input and output alphabets are transported by the machine's encoding equivalences. This supplies a finite deterministic realization with a concrete clock, rather than an assigned abstract running time.

Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeOperationalInterfaces
Formal statement
theorem Lax759944Proofs.TapeRamGenericTime.genericTime_of_lowering_finite_explicit : ∀ (lower : Lax808846.Ram.Program → Lax759944Proofs.Legacy.Ram.Program),
  (∀ (p : Lax808846.Ram.Program) (v : ℕ) (x output : List ℕ) (t : ℕ),
      (∀ a ∈ x.length :: x, a < 2 ^ v) →
        x.length + 33 < 2 ^ v →
          Lax808846.Ram.RunsTo v p (x.length :: x) output t →
            ∃ u ≤ 18 * t + 6 * (x.length + 1) + 26,
              Lax759944Proofs.Legacy.Ram.RunsTo (v + 1) (lower p) (x.length :: x) output u) →
    (∀ (x : List ℕ), x.length ≤ Lax759944.BinaryWordEncoding.bitSize x) →
      ∀ (p : Lax808846.Ram.Program) (wordBound : Polynomial ℕ),
        ∃ (H : Turing.TM2ComputableAux Lax759944.BinaryWordEncoding.Symbol Lax759944.BinaryWordEncoding.Symbol)
          (widthOverhead : Polynomial ℕ),
          (∀ (k : H.tm.K), Finite (H.tm.Γ k)) ∧
            (∀ (n : ℕ), Polynomial.eval n wordBound ≤ Polynomial.eval n widthOverhead) ∧
              ∀ (x output : List ℕ) (t : ℕ),
                Lax759944.RamPolytime.FitsInWords (Polynomial.eval (Lax759944.BinaryWordEncoding.bitSize x) wordBound)
                    (x.length :: x ++ output) →
                  Lax808846.Ram.RunsTo (Polynomial.eval (Lax759944.BinaryWordEncoding.bitSize x) widthOverhead) p
                      (x.length :: x) output t →
                    Nonempty
                      (Turing.TM2OutputsInTime H.tm
                        (List.map H.inputAlphabet.invFun (Lax759944.BinaryWordEncoding.encode x))
                        (Option.some (List.map H.outputAlphabet.invFun (Lax759944.BinaryWordEncoding.encode output)))
                        (Polynomial.eval (Lax759944.BinaryWordEncoding.bitSize x + t)
                          ((Lax759944Proofs.RamToTM.ramToTMTimePolynomial
                                (Lax759944Proofs.CellToMicrocode.compile (lower p))
                                (wordBound + Polynomial.X + Polynomial.C 7) Polynomial.X).comp
                            (Polynomial.C 100 * (Polynomial.X + 1))))) := by sorry
Source
https://github.com/szymtor/RAM-TM/blob/134e398cef46599371df99f10c9007bc34ba3868/proofs/Lax759944Proofs/TapeRamGenericTime.lean, theorem genericTime_of_lowering; mission-local explicit finite-alphabet refinement in Solutions/VerifiedRamToTMExplicitSource.lean, theorem genericTime_of_lowering_finite_explicit, using the explicit RamToTM interpreter clock.

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