Loops carrying state between rounds
Definitionsgl_loop_stateloopState: 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 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 , 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 , 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
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.
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