Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Subroutine composition carrying state

Definition
sgl_state_algebra

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Continuing on the state reached: the data-carrying counterpart of andThen.

andThen branches on a Boolean, because the model's result : State → Option Bool returns exactly one bit. That is enough for control flow but not for carrying data between subroutines. A simulation must hand the simulated machine's state — an element of Fin\ states — from the subroutine that reads the tape symbols to the one that applies the transition, and one bit will not do it.

andThenState M₁ exit M₂ runs M1M_1M1​ until it enters a state satisfying exit, then continues with M2M_2M2​ applied to that state. An arbitrary finite amount of information therefore crosses the subroutine boundary in the control rather than on a tape, which matters in a model where tapes are scarce and the state space is free.

The keystone mirrors the one for andThen: if M1M_1M1​ first exits at time aaa in state sss, then after a+1+ka + 1 + ka+1+k steps the composite is exactly M2(s)M_2(s)M2​(s) after kkk steps started on M1M_1M1​'s output tapes. Step counts add and tapes thread through, and HaltsExactly.andThenState packages this so that data-carrying compositions chain as freely as Boolean ones.

Structurally the proof is the same three-part argument — mirror the first phase, one hand-off step, mirror the continuation — with one refinement: in the first phase the composite reproduces M1M_1M1​'s behaviour including its stutter after halting, so the mirroring lemma needs no side condition relating exit to halting.

Definition code
import Definitions.Def_sgl_scratch_tapes

/-!
# Continuing on the state reached

`andThen` branches on a **`Bool`**, because the model's `result : State → Option
Bool` returns exactly one bit.  That is enough for control flow but not for
carrying *data* between subroutines: a simulation has to hand the simulated
machine's state — a `Fin states` — from the subroutine that reads the tape
symbols to the one that applies the transition.

`andThenState` closes that gap.  It runs `M₁` until it enters a state satisfying
`exit`, then continues with `M₂` applied to *that state*, so an arbitrary finite
amount of information crosses the boundary in the control rather than on a tape.

Structurally it is the same three-part argument as `andThen`: mirror `M₁` while
it has not exited, one hand-off step, then mirror the continuation.
-/

namespace SipserGacsLautemann

variable {tapes : Nat} {S₁ S₂ : Type}

/-- Run `M₁` until it reaches an `exit` state, then continue with `M₂` applied to
that state.  While in the first phase the composite mirrors `M₁` exactly,
including its stutter after halting. -/
def TypedMachine.andThenState (M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
    (M₂ : S₁ → TypedMachine tapes S₂) :
    TypedMachine tapes (S₁ ⊕ S₁ × S₂) where
  start := Sum.inl M₁.start
  transition := fun state symbols =>
    match state with
    | Sum.inl s =>
        if exit s then
          (Sum.inr (s, (M₂ s).start), fun i => (symbols i, HeadMove.stay))
        else
          match M₁.result s with
          | some _ => (Sum.inl s, fun i => (symbols i, HeadMove.stay))
          | none =>
              let action := M₁.transition s symbols
              (Sum.inl action.1, action.2)
    | Sum.inr (s, q) =>
        let action := (M₂ s).transition q symbols
        (Sum.inr (s, action.1), action.2)
  result := fun state =>
    match state with
    | Sum.inl _ => none
    | Sum.inr (s, q) => (M₂ s).result q

/-- First-phase configurations of an `andThenState` composite. -/
def TypedConfiguration.inLeftState (c : TypedConfiguration tapes S₁) :
    TypedConfiguration tapes (S₁ ⊕ S₁ × S₂) :=
  ⟨Sum.inl c.state, c.tape⟩

/-- Second-phase configurations, tagged with the state that was handed over. -/
def TypedConfiguration.inRightState (s : S₁) (c : TypedConfiguration tapes S₂) :
    TypedConfiguration tapes (S₁ ⊕ S₁ × S₂) :=
  ⟨Sum.inr (s, c.state), c.tape⟩

theorem TypedMachine.andThenState_result_inLeftState
    (M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
    (M₂ : S₁ → TypedMachine tapes S₂) (c : TypedConfiguration tapes S₁) :
    (M₁.andThenState exit M₂).result
      (TypedConfiguration.inLeftState (S₂ := S₂) c).state = none := rfl

/-- Before the exit condition fires the composite mirrors `M₁` step for step. -/
theorem TypedMachine.andThenState_iterate_left
    (M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
    (M₂ : S₁ → TypedMachine tapes S₂) (c : TypedConfiguration tapes S₁) :
    ∀ k : Nat,
      (∀ j, j < k → exit ((M₁.step^[j]) c).state = false) →
      (((M₁.andThenState exit M₂).step^[k])
          (TypedConfiguration.inLeftState c) :
        TypedConfiguration tapes (S₁ ⊕ S₁ × S₂)) =
        TypedConfiguration.inLeftState ((M₁.step^[k]) c) := by
  intro k
  induction k with
  | zero => intro _; rfl
  | succ k ih =>
      intro hfresh
      have hprev : ∀ j, j < k → exit ((M₁.step^[j]) c).state = false :=
        fun j hj => hfresh j (Nat.lt_succ_of_lt hj)
      rw [Function.iterate_succ_apply', Function.iterate_succ_apply', ih hprev]
      have hno : exit ((M₁.step^[k]) c).state = false :=
        hfresh k (Nat.lt_succ_self k)
      cases hres : M₁.result ((M₁.step^[k]) c).state with
      | some r =>
          simp [TypedMachine.step, TypedMachine.andThenState,
            TypedConfiguration.inLeftState, hno, hres,
            Tape.write_head_self, Tape.move]
      | none =>
          simp [TypedMachine.step, TypedMachine.andThenState,
            TypedConfiguration.inLeftState, hno, hres]

/-- The hand-off: the state reached selects the continuation and the tapes cross
untouched. -/
theorem TypedMachine.andThenState_step_handoff
    (M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
    (M₂ : S₁ → TypedMachine tapes S₂) {c : TypedConfiguration tapes S₁}
    (hexit : exit c.state = true) :
    (M₁.andThenState exit M₂).step (TypedConfiguration.inLeftState c) =
      TypedConfiguration.inRightState c.state
        ⟨(M₂ c.state).start, c.tape⟩ := by
  simp [TypedMachine.step, TypedMachine.andThenState,
    TypedConfiguration.inLeftState, TypedConfiguration.inRightState, hexit,
    Tape.write_head_self, Tape.move]

/-- After the hand-off the composite mirrors the continuation. -/
theorem TypedMachine.andThenState_iterate_right
    (M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
    (M₂ : S₁ → TypedMachine tapes S₂) (s : S₁)
    (c : TypedConfiguration tapes S₂) :
    ∀ k : Nat,
      (((M₁.andThenState exit M₂).step^[k])
          (TypedConfiguration.inRightState s c) :
        TypedConfiguration tapes (S₁ ⊕ S₁ × S₂)) =
        TypedConfiguration.inRightState s (((M₂ s).step^[k]) c) := by
  intro k
  induction k with
  | zero => rfl
  | succ k ih =>
      rw [Function.iterate_succ_apply', Function.iterate_succ_apply', ih]
      cases hres : (M₂ s).result (((M₂ s).step^[k]) c).state with
      | some r =>
          simp [TypedMachine.step, TypedMachine.andThenState,
            TypedConfiguration.inRightState, hres]
      | none =>
          simp [TypedMachine.step, TypedMachine.andThenState,
            TypedConfiguration.inRightState, hres]

/-- **Keystone, data-carrying form.**  If `M₁` first exits at time `a` in state
`s`, the composite after `a + 1 + k` steps is `M₂ s` after `k` steps on `M₁`'s
output tapes. -/
theorem TypedMachine.andThenState_iterate
    (M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
    (M₂ : S₁ → TypedMachine tapes S₂) (c : TypedConfiguration tapes S₁) (a : Nat)
    (hexit : exit ((M₁.step^[a]) c).state = true)
    (hfresh : ∀ j, j < a → exit ((M₁.step^[j]) c).state = false) (k : Nat) :
    (((M₁.andThenState exit M₂).step^[a + 1 + k])
        (TypedConfiguration.inLeftState c) :
      TypedConfiguration tapes (S₁ ⊕ S₁ × S₂)) =
      TypedConfiguration.inRightState ((M₁.step^[a]) c).state
        (((M₂ ((M₁.step^[a]) c).state).step^[k])
          ⟨(M₂ ((M₁.step^[a]) c).state).start, ((M₁.step^[a]) c).tape⟩) := by
  rw [show a + 1 + k = k + (1 + a) by omega,
    Function.iterate_add_apply, Function.iterate_add_apply,
    Function.iterate_one]
  rw [M₁.andThenState_iterate_left exit M₂ c a hfresh]
  rw [M₁.andThenState_step_handoff exit M₂ hexit]
  exact M₁.andThenState_iterate_right exit M₂ _ _ k

/-- **Specs compose, carrying state.**  The counterpart of
`HaltsExactly.andThen` for data-carrying hand-off. -/
theorem HaltsExactly.andThenState
    {M₁ : TypedMachine tapes S₁} {exit : S₁ → Bool}
    {M₂ : S₁ → TypedMachine tapes S₂} {c : TypedConfiguration tapes S₁}
    {a k : Nat} {v : Bool}
    (hexit : exit ((M₁.step^[a]) c).state = true)
    (hfresh : ∀ j, j < a → exit ((M₁.step^[j]) c).state = false)
    (h₂ : HaltsExactly (M₂ ((M₁.step^[a]) c).state)
      ((M₂ ((M₁.step^[a]) c).state).startCfg ((M₁.step^[a]) c).tape) k v) :
    HaltsExactly (M₁.andThenState exit M₂)
      (TypedConfiguration.inLeftState c) (a + 1 + k) v := by
  constructor
  · rw [M₁.andThenState_iterate exit M₂ c a hexit hfresh k]
    exact h₂.halts
  · intro j hj
    rcases Nat.lt_or_ge j (a + 1) with hsmall | hbig
    · have hfr : ∀ i, i < j → exit ((M₁.step^[i]) c).state = false :=
        fun i hi => hfresh i (by omega)
      rw [M₁.andThenState_iterate_left exit M₂ c j hfr]
      exact M₁.andThenState_result_inLeftState exit M₂ _
    · obtain ⟨m, hm⟩ := Nat.exists_eq_add_of_le hbig
      have hmk : m < k := by omega
      rw [hm, M₁.andThenState_iterate exit M₂ c a hexit hfresh m]
      exact h₂.fresh m hmk

end SipserGacsLautemann
Source
Standard structured-programming decomposition of Turing-machine constructions, specialized to the multitape model of Def_sipser_gacs_lautemann; extends Def_sgl_subroutine_algebra.

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