Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Configuration-tracking composition

Definition
sgl_step_chain

by Henry Yuen · Jul 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Configuration-tracking composition: the chaining tools of the step program.

The outer simulation loop's round record evaluates its next, stop and verdict functions on the round body's terminal state, so the step program's specification must pin its final configuration exactly — tapes and state. chainStepC, chainStepD and chainStepS are the configuration-tracking forms of junction composition, for constant, verdict-dispatching and state-dispatching continuations respectively: each junction contributes one inRight layer to an explicit nested terminal term, on which those functions evaluate by rfl.

carryQ sits at a chain's end with one job: place the simulated machine's next state into the terminal term where a shallow peel can find it. peelB and peelS are the layer projections; a fixed pipeline of them extracts the payload from the fixed nesting.

Definition code
import Definitions.Def_sgl_read_bits

/-!
# Configuration-tracking composition

Module E of the merge_empty plan, third part: the chaining tools for the step
program.

The outer simulation loop's `LoopRound` record evaluates `next`, `stop` and
`verdict` on the round body's **terminal state**, so the step program's
specification must pin its final configuration exactly — tapes *and* state.
`chainStepC` and `chainStepD` are the config-tracking forms of `chainStep`:
each junction contributes one `inRight` layer to an explicit nested terminal
term, on which those functions evaluate by `rfl`.

At the chain's end sits `carryQ`, whose one job is to place the simulated
machine's next state into the terminal term where a shallow peel can find it.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-! ## Config-tracking chain steps -/

/-- Constant continuation, full final configuration. -/
theorem chainStepC {S₁ S₂ : Type} {M₁ : TypedMachine tapes S₁}
    {M₂ : TypedMachine tapes S₂} {T T' : Fin tapes → Tape}
    {a : Nat} {b : Bool} {k : Nat} {v : Bool}
    (h₁ : HaltsExactly M₁ (M₁.startCfg T) a b)
    (htp : ((M₁.step^[a]) (M₁.startCfg T)).tape = T')
    (h₂ : HaltsExactly M₂ (M₂.startCfg T') k v) :
    HaltsExactly (M₁.andThen fun _ => M₂)
        ((M₁.andThen fun _ => M₂).startCfg T) (a + 1 + k) v ∧
      ((M₁.andThen fun _ => M₂).step^[a + 1 + k])
        ((M₁.andThen fun _ => M₂).startCfg T) =
        TypedConfiguration.inRight b ((M₂.step^[k]) (M₂.startCfg T')) := by
  constructor
  · exact HaltsExactly.andThen (M₂ := fun _ => M₂) h₁ (by rw [htp]; exact h₂)
  · have hcfg : (M₁.andThen fun _ => M₂).startCfg T =
        TypedConfiguration.inLeft (M₁.startCfg T) := rfl
    rw [hcfg, TypedMachine.andThen_iterate M₁ (fun _ => M₂) _ a b h₁.halts
      h₁.fresh k, htp]
    rfl

/-- Verdict-dispatching continuation, full final configuration. -/
theorem chainStepD {S₁ S₂ : Type} {M₁ : TypedMachine tapes S₁}
    (M₂ : Bool → TypedMachine tapes S₂) {T T' : Fin tapes → Tape}
    {a : Nat} {b : Bool} {k : Nat} {v : Bool}
    (h₁ : HaltsExactly M₁ (M₁.startCfg T) a b)
    (htp : ((M₁.step^[a]) (M₁.startCfg T)).tape = T')
    (h₂ : HaltsExactly (M₂ b) ((M₂ b).startCfg T') k v) :
    HaltsExactly (M₁.andThen M₂) ((M₁.andThen M₂).startCfg T) (a + 1 + k) v ∧
      ((M₁.andThen M₂).step^[a + 1 + k]) ((M₁.andThen M₂).startCfg T) =
        TypedConfiguration.inRight b
          (((M₂ b).step^[k]) ((M₂ b).startCfg T')) := by
  constructor
  · exact HaltsExactly.andThen h₁ (by rw [htp]; exact h₂)
  · have hcfg : (M₁.andThen M₂).startCfg T =
        TypedConfiguration.inLeft (M₁.startCfg T) := rfl
    rw [hcfg, TypedMachine.andThen_iterate M₁ M₂ _ a b h₁.halts h₁.fresh k,
      htp]
    rfl

/-- State-dispatching continuation (through `andThenState`), full final
configuration.  The first machine's exit state is remembered in the composite's
terminal term. -/
theorem chainStepS {S₁ S₂ : Type} {M₁ : TypedMachine tapes S₁}
    {exit : S₁ → Bool} (M₂ : S₁ → TypedMachine tapes S₂)
    {T T' : Fin tapes → Tape} {a : Nat} {st : S₁} {k : Nat} {v : Bool}
    (hexit : exit ((M₁.step^[a]) (M₁.startCfg T)).state = true)
    (hfresh : ∀ j, j < a →
      exit ((M₁.step^[j]) (M₁.startCfg T)).state = false)
    (hst : ((M₁.step^[a]) (M₁.startCfg T)).state = st)
    (htp : ((M₁.step^[a]) (M₁.startCfg T)).tape = T')
    (h₂ : HaltsExactly (M₂ st) ((M₂ st).startCfg T') k v) :
    HaltsExactly (M₁.andThenState exit M₂)
        ((M₁.andThenState exit M₂).startCfg T) (a + 1 + k) v ∧
      ((M₁.andThenState exit M₂).step^[a + 1 + k])
        ((M₁.andThenState exit M₂).startCfg T) =
        TypedConfiguration.inRightState st
          (((M₂ st).step^[k]) ((M₂ st).startCfg T')) := by
  have hcfg : (M₁.andThenState exit M₂).startCfg T =
      TypedConfiguration.inLeftState (M₁.startCfg T) := rfl
  constructor
  · rw [hcfg]
    exact HaltsExactly.andThenState hexit hfresh (by rw [hst, htp]; exact h₂)
  · rw [hcfg, TypedMachine.andThenState_iterate M₁ exit M₂ _ a hexit hfresh k,
      hst, htp]
    rfl

/-! ## Carrying the next state out of the chain -/

/-- Halt after one step, with a payload in the state where the loop's `next`
function can read it. -/
def carryQ {Q : Type} (q : Q) : TypedMachine tapes (Option Q) where
  start := none
  transition := fun _ symbols => (some q, fun j => (symbols j, HeadMove.stay))
  result := fun s => match s with
    | some _ => some false
    | none => none

theorem carryQ_run {Q : Type} (q : Q) (tape : Fin tapes → Tape) :
    ((carryQ (tapes := tapes) q).step^[1]) ((carryQ q).startCfg tape) =
      ⟨some q, tape⟩ := by
  show (carryQ q).step ((carryQ q).startCfg tape) = _
  simp only [TypedMachine.step, carryQ]
  congr 1


theorem carryQ_spec {Q : Type} (q : Q) (tape : Fin tapes → Tape) :
    HaltsExactly (carryQ (tapes := tapes) q) ((carryQ q).startCfg tape) 1
      false := by
  constructor
  · rw [carryQ_run]
    rfl
  · intro j hj
    have : j = 0 := by omega
    subst this
    rfl

/-! ## Peeling the terminal term -/

/-- One `andThen` layer of a terminal state. -/
def peelB {S₁ S₂ : Type} : S₁ ⊕ Bool × S₂ → Option S₂
  | .inr (_, s) => some s
  | .inl _ => none

/-- One `andThenState` layer of a terminal state. -/
def peelS {S₁ S₂ : Type} : S₁ ⊕ S₁ × S₂ → Option S₂
  | .inr (_, s) => some s
  | .inl _ => none

@[simp] theorem peelB_inRight {S₁ S₂ : Type} (b : Bool)
    (c : TypedConfiguration tapes S₂) :
    peelB (S₁ := S₁) (TypedConfiguration.inRight b c).state = some c.state :=
  rfl

@[simp] theorem peelS_inRightState {S₁ S₂ : Type} (st : S₁)
    (c : TypedConfiguration tapes S₂) :
    peelS (TypedConfiguration.inRightState st c).state = some c.state := rfl

end SipserGacsLautemann
Source
Composition machinery for the two-track simulation's step program; builds on Def_sgl_read_bits.

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