Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Whole-subroutine native work-lane compilation with exact transient resources

Proved
CatalyticTreeEval.Contracts.WorkLanes.framed_firstExit

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

Fix a native source machine A, K lanes and a lane j<K. Suppose an initialized physical tape represents the source work tape at addresses b+(K+1)p+j and has a true origin marker only at row zero. If A first halts after T transitions with a work-head bound B, catalyst-head envelope and writable footprint, then the actual fixed finite compiled machine first halts after

T(2(K−j)+1+K)T(2(K-j)+1+K)T(2(K−j)+1+K)

transitions. Every intermediate native work head lies in [b,b+(K+1)B)[b,b+(K+1)B)[b,b+(K+1)B), the catalyst envelope is retained, and the writable work footprint is mapped by the lane addressing. Every inactive work lane is preserved exactly. The endpoint represents the exact source endpoint, including output, catalyst and heads. The table is fixed before input, tape contents, workspace width and T; origin initialization is an explicit precondition.

Preamble
import Definitions.Def_CatalyticTreeEval_WorkLaneContracts
Formal statement
namespace CatalyticTreeEval.Contracts.WorkLanes

theorem framed_firstExit (A : CatalyticTreeEval.Main.Machine) (lanes : ℕ) (lane : Fin lanes) (base : ℕ)
    (input : List Bool) (source target : CatalyticMatching.General.Configuration A)
    (physical : ℕ → Bool) (T : ℕ) (E : CatalyticTreeEval.Contracts.Envelope)
    (F : CatalyticTreeEval.Contracts.Footprint)
    (hi : source.inputHead ≤ input.length + 1)
    (hc : source.catalystHead ≤ source.catalyst.length)
    (origin : CatalyticTreeEval.Contracts.WorkLanes.OriginTrack lanes base physical)
    (workMatches : CatalyticTreeEval.Contracts.WorkLanes.Matches lane base source.work physical)
    (H : CatalyticTreeEval.Contracts.FirstExit (A.step input)
      (fun _ d => E.Contains d ∧ CatalyticTreeEval.Contracts.SameOutside F source d)
      {d | d.state = none} source target T) :
    ∃ updated : ℕ → Bool,
      CatalyticTreeEval.Contracts.WorkLanes.OriginTrack lanes base updated ∧
      CatalyticTreeEval.Contracts.WorkLanes.Matches lane base target.work updated ∧
      CatalyticTreeEval.Contracts.WorkLanes.Inactive lane base physical updated ∧
      CatalyticTreeEval.Contracts.FirstExit
        ((CatalyticTreeEval.Contracts.WorkLanes.machine A lanes lane).step input)
        (fun _ e => (CatalyticTreeEval.Contracts.WorkLanes.liftedEnvelope lanes base E).Contains e ∧
          CatalyticTreeEval.Contracts.SameOutside
            (CatalyticTreeEval.Contracts.WorkLanes.liftedFootprint lane base F)
            (CatalyticTreeEval.Contracts.WorkLanes.embed A lanes lane base source physical) e)
        {e | e.state = none}
        (CatalyticTreeEval.Contracts.WorkLanes.embed A lanes lane base source physical)
        (CatalyticTreeEval.Contracts.WorkLanes.embed A lanes lane base target updated)
        (T * CatalyticTreeEval.Contracts.WorkLanes.macroTime lane) := by
  sorry

end CatalyticTreeEval.Contracts.WorkLanes
Source
Infrastructure for Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, native uniform arithmetic and finite-control subroutine composition.

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