Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Loops carrying state between rounds

Definition
sgl_loop_state

by Henry Yuen · Jul 25, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

loopState: a loop whose body is a family indexed by a loop-carried value.

repeatUntilFalse re-enters its body at the fixed body.start, so all control state is erased between rounds. That is deliberate — it is what forces loop counters onto the tapes, and it is why an input-dependent number of rounds is expressible at all. But it makes the combinator unable to express a simulation, whose rounds must carry the simulated machine's state qqq from each round to the next. The same failure recurs one level down: a sweep that reads a symbol partway along must still know it when the sweep ends.

loopState closes this. The body is a family body:Carry→TypedMachine\mathrm{body} : \mathrm{Carry} \to \mathrm{TypedMachine}body:Carry→TypedMachine, so the carried value is a parameter of the round's program rather than something threaded at runtime — every dispatch inside a round receives it by construction. That is the same device that makes andThenState work, lifted from a single hand-off to an unbounded iteration. Taking the carried type to be trivial recovers repeatUntilFalse as the degenerate instance.

The round record. LoopRound packages, for round iii, everything the induction over rounds needs: that the round's body halts on schedule, that the stopping condition does not fire, and the two equations locating the next round's carried value and configuration. Bundling these in one record rather than as loose conjuncts is what keeps the induction to a single hypothesis — the alternative is the sort of ad-hoc accumulation that produces unmaintainable proofs.

The specification. loopState_spec states that given per-round records and a final round that stops, the entire loop is one HaltsExactly obligation of cost

loopCost(c,r)+a  =  (∑i<r(ci+1))+a,\mathrm{loopCost}(c, r) + a \;=\; \Big(\sum_{i<r} (c_i + 1)\Big) + a ,loopCost(c,r)+a=(i<r∑​(ci​+1))+a,

each round paying its body plus a single re-entry step. Loops therefore remain first-class subroutines and nest inside andThen chains exactly as before, now while carrying state.

Definition code
import Definitions.Def_sgl_fires_exactly

/-!
# `loopState`: a loop whose body is indexed by a carried value

Module B of the merge_empty plan (`DESIGN_merge_empty_v2.md`), and its critical
path.

`repeatUntilFalse` re-enters its body at the fixed `body.start`, so every bit of
control state is erased between rounds.  That is deliberate — it is what puts
loop counters on the tapes — and it makes the combinator unable to express a
simulation, whose rounds must carry the simulated machine's state from one to
the next.

`loopState` fixes this by making the body a **family** `Carry → TypedMachine`
indexed by a loop-carried value.  The value is a Lean-level parameter of each
round's program, so every dispatch inside a round receives it by construction
and nothing threads it at runtime — the same move that makes `andThenState`
work.  `repeatUntilFalse` is the degenerate instance `Σ := Unit`.

The round-to-round data is packaged by `LoopRound`, which carries in one record
both the halting spec of the round's body and the tape/value bookkeeping, so
that the induction over rounds has a single hypothesis to consume.
-/

namespace SipserGacsLautemann

variable {tapes : Nat} {Carry B : Type}

/-- Run `body s`; when it halts, either stop — reporting `verdict s` of the
halting state — or re-enter with the carried value advanced by `next`. -/
def TypedMachine.loopState
    (body : Carry → TypedMachine tapes B)
    (next : Carry → B → Carry) (stop : Carry → B → Bool) (verdict : Carry → B → Bool)
    (s₀ : Carry) : TypedMachine tapes (Carry × B) where
  start := (s₀, (body s₀).start)
  transition := fun state symbols =>
    match (body state.1).result state.2 with
    | some _ =>
        if stop state.1 state.2 then
          (state, fun i => (symbols i, HeadMove.stay))
        else
          ((next state.1 state.2,
              (body (next state.1 state.2)).start),
            fun i => (symbols i, HeadMove.stay))
    | none =>
        let action := (body state.1).transition state.2 symbols
        ((state.1, action.1), action.2)
  result := fun state =>
    match (body state.1).result state.2 with
    | some _ =>
        if stop state.1 state.2 then some (verdict state.1 state.2) else none
    | none => none

/-- Configurations of the loop, tagged with the carried value. -/
def TypedConfiguration.inLoop (s : Carry) (c : TypedConfiguration tapes B) :
    TypedConfiguration tapes (Carry × B) :=
  ⟨(s, c.state), c.tape⟩

section
variable (body : Carry → TypedMachine tapes B)
    (next : Carry → B → Carry) (stop : Carry → B → Bool) (verdict : Carry → B → Bool)

/-- Within a round the loop mirrors that round's body, the carried value staying
fixed. -/
theorem TypedMachine.loopState_iterate_body (s₀ s : Carry)
    (c : TypedConfiguration tapes B) :
    ∀ k : Nat,
      (∀ j, j < k → (body s).result (((body s).step^[j]) c).state = none) →
      (((TypedMachine.loopState body next stop verdict s₀).step^[k])
          (TypedConfiguration.inLoop s c) :
        TypedConfiguration tapes (Carry × B)) =
        TypedConfiguration.inLoop s (((body s).step^[k]) c) := by
  intro k
  induction k with
  | zero => intro _; rfl
  | succ k ih =>
      intro hfresh
      have hprev :
          ∀ j, j < k → (body s).result (((body s).step^[j]) c).state = none :=
        fun j hj => hfresh j (Nat.lt_succ_of_lt hj)
      rw [Function.iterate_succ_apply', Function.iterate_succ_apply', ih hprev]
      have hnone : (body s).result (((body s).step^[k]) c).state = none :=
        hfresh k (Nat.lt_succ_self k)
      simp [TypedMachine.step, TypedMachine.loopState,
        TypedConfiguration.inLoop, hnone]

/-- The re-entry step: a round that halts without stopping restarts the body at
the advanced carried value, on the round's output tapes. -/
theorem TypedMachine.loopState_step_reenter (s₀ s : Carry)
    {c : TypedConfiguration tapes B} {r : Bool}
    (hhalt : (body s).result c.state = some r)
    (hstop : stop s c.state = false) :
    (TypedMachine.loopState body next stop verdict s₀).step
        (TypedConfiguration.inLoop s c) =
      TypedConfiguration.inLoop (next s c.state)
        ⟨(body (next s c.state)).start, c.tape⟩ := by
  simp [TypedMachine.step, TypedMachine.loopState, TypedConfiguration.inLoop,
    hhalt, hstop, Tape.write_head_self, Tape.move]

/-- A round that halts and stops leaves the loop halted with its verdict. -/
theorem TypedMachine.loopState_result_stop (s₀ s : Carry)
    {c : TypedConfiguration tapes B} {r : Bool}
    (hhalt : (body s).result c.state = some r)
    (hstop : stop s c.state = true) :
    (TypedMachine.loopState body next stop verdict s₀).result
        (TypedConfiguration.inLoop s c).state =
      some (verdict s c.state) := by
  simp [TypedMachine.loopState, TypedConfiguration.inLoop, hhalt, hstop]

/-- Nothing halts the loop strictly inside a round. -/
theorem TypedMachine.loopState_pre_fresh (s₀ s : Carry)
    (c : TypedConfiguration tapes B) (a : Nat) (v : Bool)
    (h : HaltsExactly (body s) c a v) :
    ∀ t, t < a →
      (TypedMachine.loopState body next stop verdict s₀).result
        (((TypedMachine.loopState body next stop verdict s₀).step^[t])
          (TypedConfiguration.inLoop s c)).state = none := by
  intro t ht
  rw [TypedMachine.loopState_iterate_body body next stop verdict s₀ s c t
    (fun j hj => h.fresh j (by omega))]
  simp [TypedMachine.loopState, TypedConfiguration.inLoop, h.fresh t ht]

/-- Nor at the end of a round that does not stop. -/
theorem TypedMachine.loopState_round_fresh (s₀ s : Carry)
    (c : TypedConfiguration tapes B) (a : Nat) (v : Bool)
    (h : HaltsExactly (body s) c a v)
    (hstop : stop s (((body s).step^[a]) c).state = false) :
    ∀ t, t < a + 1 →
      (TypedMachine.loopState body next stop verdict s₀).result
        (((TypedMachine.loopState body next stop verdict s₀).step^[t])
          (TypedConfiguration.inLoop s c)).state = none := by
  intro t ht
  rcases Nat.lt_or_ge t a with hlt | hge
  · exact TypedMachine.loopState_pre_fresh body next stop verdict s₀ s c a v h t hlt
  · have hta : t = a := by omega
    subst hta
    rw [TypedMachine.loopState_iterate_body body next stop verdict s₀ s c t h.fresh]
    simp [TypedMachine.loopState, TypedConfiguration.inLoop, h.halts, hstop]

end

/-! ## The round record

One structure carrying everything the induction needs about round `i`: which
carried value and configuration it starts from, that its body halts on schedule
without stopping, and that the next round begins where this one left off. -/

/-- Round `i` of a `loopState` run. -/
structure LoopRound {tapes : Nat} {Carry B : Type}
    (body : Carry → TypedMachine tapes B) (next : Carry → B → Carry)
    (stop : Carry → B → Bool)
    (carry : Nat → Carry) (config : Nat → TypedConfiguration tapes B)
    (cost : Nat → Nat) (i : Nat) : Prop where
  halts : ∃ v : Bool, HaltsExactly (body (carry i)) (config i) (cost i) v
  keeps : stop (carry i) (((body (carry i)).step^[cost i]) (config i)).state = false
  carry_succ :
    carry (i + 1) = next (carry i) (((body (carry i)).step^[cost i]) (config i)).state
  config_succ :
    config (i + 1) =
      ⟨(body (carry (i + 1))).start,
        (((body (carry i)).step^[cost i]) (config i)).tape⟩

section
variable (body : Carry → TypedMachine tapes B)
    (next : Carry → B → Carry) (stop : Carry → B → Bool) (verdict : Carry → B → Bool)

/-- One round advances the loop by `cost i + 1` steps to the next round's
configuration. -/
theorem TypedMachine.loopState_round (s₀ : Carry)
    (carry : Nat → Carry) (config : Nat → TypedConfiguration tapes B)
    (cost : Nat → Nat) (i : Nat)
    (hround : LoopRound body next stop carry config cost i) :
    (((TypedMachine.loopState body next stop verdict s₀).step^[cost i + 1])
        (TypedConfiguration.inLoop (carry i) (config i)) :
      TypedConfiguration tapes (Carry × B)) =
      TypedConfiguration.inLoop (carry (i + 1)) (config (i + 1)) := by
  obtain ⟨v, hv⟩ := hround.halts
  rw [Function.iterate_succ_apply',
    TypedMachine.loopState_iterate_body body next stop verdict s₀ (carry i)
      (config i) (cost i) hv.fresh,
    TypedMachine.loopState_step_reenter body next stop verdict s₀ (carry i)
      hv.halts hround.keeps,
    hround.config_succ, hround.carry_succ]

/-- After `rounds` complete rounds the loop stands at round `rounds`.
The total cost is `loopCost cost rounds = Σ (cost i + 1)`: each round pays its
body plus the single re-entry step. -/
theorem TypedMachine.loopState_rounds (s₀ : Carry)
    (carry : Nat → Carry) (config : Nat → TypedConfiguration tapes B)
    (cost : Nat → Nat) (rounds : Nat)
    (hround : ∀ i, i < rounds → LoopRound body next stop carry config cost i) :
    (((TypedMachine.loopState body next stop verdict s₀).step^[
          loopCost cost rounds])
        (TypedConfiguration.inLoop (carry 0) (config 0)) :
      TypedConfiguration tapes (Carry × B)) =
      TypedConfiguration.inLoop (carry rounds) (config rounds) := by
  induction rounds with
  | zero => rfl
  | succ rounds ih =>
      rw [loopCost, Nat.add_comm (loopCost cost rounds) (cost rounds + 1),
        Function.iterate_add_apply,
        ih (fun i hi => hround i (Nat.lt_succ_of_lt hi)),
        TypedMachine.loopState_round body next stop verdict s₀ carry config cost
          rounds (hround rounds (Nat.lt_succ_self rounds))]

/-- **The loop as a subroutine.**  Given per-round records and a final round
that stops, the whole loop is a `HaltsExactly` obligation of cost
`loopCost cost rounds + a`, and therefore composes with `andThen`. -/
theorem TypedMachine.loopState_spec (s₀ : Carry)
    (carry : Nat → Carry) (config : Nat → TypedConfiguration tapes B)
    (cost : Nat → Nat) (rounds : Nat) (a : Nat) (v : Bool)
    (hround : ∀ i, i < rounds → LoopRound body next stop carry config cost i)
    (hexit : HaltsExactly (body (carry rounds)) (config rounds) a v)
    (hstop : stop (carry rounds)
      (((body (carry rounds)).step^[a]) (config rounds)).state = true)
    (hverdict : verdict (carry rounds)
      (((body (carry rounds)).step^[a]) (config rounds)).state = v) :
    HaltsExactly (TypedMachine.loopState body next stop verdict s₀)
      (TypedConfiguration.inLoop (carry 0) (config 0))
      (loopCost cost rounds + a) v := by
  have hrun :=
    TypedMachine.loopState_rounds body next stop verdict s₀ carry config cost
      rounds hround
  constructor
  · rw [Nat.add_comm, Function.iterate_add_apply, hrun,
      TypedMachine.loopState_iterate_body body next stop verdict s₀
        (carry rounds) (config rounds) a hexit.fresh,
      TypedMachine.loopState_result_stop body next stop verdict s₀
        (carry rounds) hexit.halts hstop, hverdict]
  · intro j hj
    rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt | hge
    · -- inside the completed rounds
      clear hrun hexit hstop hverdict hj
      induction rounds with
      | zero => simp [loopCost] at hlt
      | succ rounds ih =>
          rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt' | hge'
          · exact ih (fun i hi => hround i (Nat.lt_succ_of_lt hi)) hlt'
          · obtain ⟨t, ht⟩ := Nat.exists_eq_add_of_le hge'
            have htlt : t < cost rounds + 1 := by
              rw [loopCost] at hlt; omega
            obtain ⟨v', hv'⟩ := (hround rounds (Nat.lt_succ_self rounds)).halts
            rw [ht, Nat.add_comm, Function.iterate_add_apply,
              TypedMachine.loopState_rounds body next stop verdict s₀ carry
                config cost rounds
                (fun i hi => hround i (Nat.lt_succ_of_lt hi))]
            exact TypedMachine.loopState_round_fresh body next stop verdict s₀
              (carry rounds) (config rounds) (cost rounds) v' hv'
              (hround rounds (Nat.lt_succ_self rounds)).keeps t htlt
    · obtain ⟨t, ht⟩ := Nat.exists_eq_add_of_le hge
      have htlt : t < a := by omega
      rw [ht, Nat.add_comm, Function.iterate_add_apply, hrun]
      exact TypedMachine.loopState_pre_fresh body next stop verdict s₀
        (carry rounds) (config rounds) a v hexit t htlt

end

end SipserGacsLautemann
Source
Structured-programming decomposition of Turing-machine constructions, specialized to the model of Def_sipser_gacs_lautemann; extends Def_sgl_subroutine_algebra and supports Def_sgl_scratch_tapes.

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