Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The cellwise loop engine

Definition
sgl_cellwise_engine

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The cellwise loop engine: an arbitrary local action, looped until a guard tape goes blank.

sgl_tape_navigation proved a scan by looping a head move until reaching a blank. Copying, XOR-ing and block extraction share that control structure exactly and differ only in the local action performed at each cell. Rather than repeat the argument once per macro, this module generalises it.

cellwiseLoop_spec_of takes an arbitrary local action and a guard tape and concludes that the loop is a subroutine of cost 4d+34d+34d+3, where ddd is the number of rounds. Its companion cellwiseLoop_tape_of describes the output: the tapes are the action iterated d+1d+1d+1 times, written actTapes tape action (d+1) — a purely functional description with no machine in it. The action is opaque to both proofs.

Supporting this is repeatUntilFalse_tape, the counterpart to repeatUntilFalse_spec of the subroutine algebra: where that says when a loop halts, this says what it leaves behind.

The consequence is the point of the module. Every macro built above it reduces to two statements about actTapes — how the guard tape evolves, and what the iterated action computes — and neither mentions a machine. All Turing-machine reasoning in the plumbing stops here.

Definition code
import Definitions.Def_sgl_tape_navigation

/-!
# The cellwise loop engine

`sgl_tape_navigation` proved a scan by looping a *head move* until a blank.
Copying, XOR-ing and block extraction have exactly the same control structure
and differ only in the local action performed at each cell.  So rather than
repeat that argument once per macro, this module generalises it:
`cellwiseLoop_spec_of` takes an **arbitrary** local action and concludes both a
`HaltsExactly` specification and the resulting tapes.

The consequence is that every remaining macro's obligation is a statement about
`actTapes` — iterating a pure function on tapes — with no machine content at
all.  All Turing-machine reasoning in the plumbing stops here.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-! ## Loops and tapes

`repeatUntilFalse_spec` says when a loop halts; this says what it leaves behind. -/

theorem TypedMachine.repeatUntilFalse_tape {S : Type}
    (body : TypedMachine tapes S)
    (config : Nat → TypedConfiguration tapes S) (cost : Nat → Nat)
    (rounds : Nat) (a : Nat)
    (hround : ∀ i, i < rounds →
      HaltsExactly body (config i) (cost i) true ∧
        config (i + 1) = ⟨body.start, ((body.step^[cost i]) (config i)).tape⟩)
    (hexit : HaltsExactly body (config rounds) a false) :
    ((body.repeatUntilFalse.step^[loopCost cost rounds + a]) (config 0)).tape =
      ((body.step^[a]) (config rounds)).tape := by
  rw [Nat.add_comm, Function.iterate_add_apply,
    body.repeatUntilFalse_rounds config cost rounds hround,
    body.repeatUntilFalse_iterate_fresh (config rounds) a hexit.fresh]

/-! ## Iterating a local action -/

/-- The tapes after `n` applications of a local action. -/
def actTapes (tape : Fin tapes → Tape)
    (action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove)) :
    Nat → (Fin tapes → Tape)
  | 0 => tape
  | n + 1 => applyAction (actTapes tape action n) action

/-- Loop a local action, continuing while tape `guard`'s head is written. -/
def cellwiseBody
    (action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
    (guard : Fin tapes) : TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
  (TypedMachine.act action).andThen
    (fun _ => TypedMachine.test (notBlankAt guard))

def cellwiseLoop
    (action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
    (guard : Fin tapes) : TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
  (cellwiseBody action guard).repeatUntilFalse

theorem cellwiseBody_round
    (action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
    (guard : Fin tapes) (tape : Fin tapes → Tape) (m : Nat) :
    HaltsExactly (cellwiseBody action guard)
      ((cellwiseBody action guard).startCfg (actTapes tape action m)) (1 + 1 + 1)
      (notBlankAt guard (fun j => ((actTapes tape action (m + 1)) j).head)) := by
  have h₂ :
      HaltsExactly (TypedMachine.test (notBlankAt guard))
        ((TypedMachine.test (notBlankAt guard)).startCfg
          (((TypedMachine.act action).step^[1])
            ((TypedMachine.act action).startCfg
              (actTapes tape action m))).tape) 1
        (notBlankAt guard
          (fun j => ((actTapes tape action (m + 1)) j).head)) := by
    rw [TypedMachine.act_tape]
    exact TypedMachine.test_spec (notBlankAt guard) _
  exact HaltsExactly.andThen
    (TypedMachine.act_spec action (actTapes tape action m)) h₂

theorem cellwiseBody_round_tape
    (action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
    (guard : Fin tapes) (tape : Fin tapes → Tape) (m : Nat) :
    (((cellwiseBody action guard).step^[1 + 1 + 1])
        ((cellwiseBody action guard).startCfg (actTapes tape action m))).tape =
      actTapes tape action (m + 1) := by
  have h := TypedMachine.doWhile_round_tape
    (TypedMachine.act action) (notBlankAt guard) (actTapes tape action m) 1 true
    (TypedMachine.act_spec action (actTapes tape action m)).halts
    (TypedMachine.act_spec action (actTapes tape action m)).fresh
  rw [TypedMachine.act_tape] at h
  exact h

/-- Round `m` continues exactly when the guard is still on written tape. -/
theorem cellwiseLoop_rounds
    (action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
    (guard : Fin tapes) (tape : Fin tapes → Tape) (d : Nat)
    (hlt : ∀ k, k < d →
      ((actTapes tape action (k + 1)) guard).head ≠ TapeSymbol.blank) :
    ∀ m, m < d →
      HaltsExactly (cellwiseBody action guard)
          ((cellwiseBody action guard).startCfg (actTapes tape action m))
          (1 + 1 + 1) true ∧
        (cellwiseBody action guard).startCfg (actTapes tape action (m + 1)) =
          ⟨(cellwiseBody action guard).start,
            (((cellwiseBody action guard).step^[1 + 1 + 1])
              ((cellwiseBody action guard).startCfg
                (actTapes tape action m))).tape⟩ := by
  intro m hm
  refine ⟨?_, ?_⟩
  · have h := cellwiseBody_round action guard tape m
    rwa [notBlankAt_true guard (actTapes tape action (m + 1)) (hlt m hm)] at h
  · rw [cellwiseBody_round_tape]
    rfl

theorem cellwiseLoop_exit
    (action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
    (guard : Fin tapes) (tape : Fin tapes → Tape) (d : Nat)
    (heq : ((actTapes tape action (d + 1)) guard).head = TapeSymbol.blank) :
    HaltsExactly (cellwiseBody action guard)
      ((cellwiseBody action guard).startCfg (actTapes tape action d))
      (1 + 1 + 1) false := by
  have h := cellwiseBody_round action guard tape d
  rwa [notBlankAt_false guard (actTapes tape action (d + 1)) heq] at h

/-- **The engine.**  An arbitrary local action, looped until the guard tape goes
blank, is a subroutine of cost `4d + 3`.  The action is opaque to the proof, so
each concrete macro costs only the tape-level facts below. -/
theorem cellwiseLoop_spec_of
    (action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
    (guard : Fin tapes) (tape : Fin tapes → Tape) (d : Nat)
    (hlt : ∀ k, k < d →
      ((actTapes tape action (k + 1)) guard).head ≠ TapeSymbol.blank)
    (heq : ((actTapes tape action (d + 1)) guard).head = TapeSymbol.blank) :
    HaltsExactly (cellwiseLoop action guard)
      ((cellwiseLoop action guard).startCfg tape) (d * 4 + 3) false := by
  have hloop :=
    TypedMachine.repeatUntilFalse_spec (cellwiseBody action guard)
      (fun m => (cellwiseBody action guard).startCfg (actTapes tape action m))
      (fun _ => 1 + 1 + 1) d (1 + 1 + 1)
      (cellwiseLoop_rounds action guard tape d hlt)
      (cellwiseLoop_exit action guard tape d heq)
  rw [loopCost_const] at hloop
  exact hloop

/-- **And what it leaves behind.**  The engine's output tapes are the action
iterated `d + 1` times — a purely functional description, with no machine in
it. -/
theorem cellwiseLoop_tape_of
    (action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
    (guard : Fin tapes) (tape : Fin tapes → Tape) (d : Nat)
    (hlt : ∀ k, k < d →
      ((actTapes tape action (k + 1)) guard).head ≠ TapeSymbol.blank)
    (heq : ((actTapes tape action (d + 1)) guard).head = TapeSymbol.blank) :
    (((cellwiseLoop action guard).step^[d * 4 + 3])
        ((cellwiseLoop action guard).startCfg tape)).tape =
      actTapes tape action (d + 1) := by
  have h :=
    TypedMachine.repeatUntilFalse_tape (cellwiseBody action guard)
      (fun m => (cellwiseBody action guard).startCfg (actTapes tape action m))
      (fun _ => 1 + 1 + 1) d (1 + 1 + 1)
      (cellwiseLoop_rounds action guard tape d hlt)
      (cellwiseLoop_exit action guard tape d heq)
  rw [loopCost_const] at h
  rw [cellwiseBody_round_tape] at h
  exact h

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

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