Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Tape macros and the loop-to-subroutine bridge

Definition
sgl_machine_macros

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Tape macros built on sgl_machine_algebra, together with the generic bridge from a loop to a subroutine specification.

The loop as a subroutine. repeatUntilFalse_rounds locates a loop at its round boundaries, but to feed a loop into HaltsExactly.andThen one also needs that it does not halt in between. repeatUntilFalse_spec closes that gap once and for all: given per-round specifications and a final round reporting false, the entire loop is a subroutine of cost

loopCost(c,r)+a  =  (∑m<r(cm+1))+a,\mathrm{loopCost}(c, r) + a \;=\; \Big(\sum_{m<r} (c_m + 1)\Big) + a ,loopCost(c,r)+a=(m<r∑​(cm​+1))+a,

and therefore composes with everything else. loopCost_const evaluates this to r(c+1)+ar(c+1) + ar(c+1)+a for a constant per-round cost.

The scanning macro. scanRightToBlank i advances tape iii's head to the first blank strictly to the right of its current position, leaving every other tape untouched. Writing ddd for the distance to that blank, its specification is

HaltsExactly  (scanRightToBlank  i)    (4d+3)    false.\mathrm{HaltsExactly}\;(\mathrm{scanRightToBlank}\; i)\;\;(4d + 3)\;\;\mathsf{false}.HaltsExactly(scanRightToBlanki)(4d+3)false.

The step count is a function of the tape contents, not a numeral. This is the situation a finite, input-independent state space cannot express by itself, and it is precisely what the tape-resident loop counter of repeatUntilFalse buys: locating the end of a written region is the primitive on which block selection, copying and counter manipulation all rest.

Method. The tape-level content is a single induction, blank_scan_spec, proving in one pass that the head reads a written cell at every distance below ddd and a blank at distance d+1d+1d+1. Everything above that line is assembled through the algebra: the round specification comes from HaltsExactly.andThen, the loop specification from repeatUntilFalse_spec, and no proof in the assembly mentions step or run at all. That separation is the intended working style for the remaining macros — rewind, copy, xorInto, blockSelect, counter increment and compare, and the majority fold — each of which needs its own small tape induction and then composes without further machine reasoning.

Definition code
import Definitions.Def_sgl_machine_algebra

/-!
# Tape macros built on the machine algebra

The algebra of `Def_sgl_machine_algebra` reduces machine construction to
straight-line code, branching and bounded iteration.  This module is the first
consumer: it builds the scanning macro every scheduler needs — "advance a head
to the end of the string it is sitting on" — and proves its `HaltsExactly`
specification, with an **input-dependent** step count, entirely through the
algebra.

The point of interest is that the step count is not a numeral: it is
`4 * blankIndex r + 3`, a function of the tape contents.  That is exactly the
situation a finite state space cannot express by itself, and it is handled here
by `repeatUntilFalse`, whose loop counter lives on the tape.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-! ## Tape-level arithmetic

Pure statements about `Tape.move`; no machines yet. -/

/-- One step of the head to the right. -/
def moveRight (tape : Tape) : Tape := Tape.move tape .right

/-- Distance from the head to the first blank strictly to its right.  Cells past
the end of the written region are blank, so this is total. -/
def blankIndex : List TapeSymbol → Nat
  | [] => 0
  | TapeSymbol.blank :: _ => 0
  | TapeSymbol.bit _ :: rest => blankIndex rest + 1

theorem moveRight_cons_bit (left : List TapeSymbol) (head : TapeSymbol)
    (b : Bool) (rest : List TapeSymbol) :
    moveRight ⟨left, head, TapeSymbol.bit b :: rest⟩ =
      ⟨head :: left, TapeSymbol.bit b, rest⟩ := rfl

/-- Before reaching the first blank the head always reads a written cell, and at
distance `blankIndex r + 1` it reads a blank.  Both halves at once, so the
induction on the tape's right-hand contents runs only once. -/
theorem blank_scan_spec :
    ∀ (right : List TapeSymbol) (left : List TapeSymbol) (head : TapeSymbol),
      (∀ k, k < blankIndex right →
          (moveRight^[k + 1] ⟨left, head, right⟩).head ≠ TapeSymbol.blank) ∧
        (moveRight^[blankIndex right + 1] ⟨left, head, right⟩).head =
          TapeSymbol.blank := by
  intro right
  induction right with
  | nil =>
      intro left head
      refine ⟨?_, ?_⟩
      · intro k hk; simp [blankIndex] at hk
      · simp [blankIndex, moveRight, Tape.move]
  | cons symbol rest ih =>
      intro left head
      cases symbol with
      | blank =>
          refine ⟨?_, ?_⟩
          · intro k hk; simp [blankIndex] at hk
          · simp [blankIndex, moveRight, Tape.move]
      | bit b =>
          obtain ⟨ihlt, iheq⟩ := ih (head :: left) (TapeSymbol.bit b)
          refine ⟨?_, ?_⟩
          · intro k hk
            rw [Function.iterate_succ_apply, moveRight_cons_bit]
            cases k with
            | zero => simp
            | succ k =>
                exact ihlt k (by simp [blankIndex] at hk; omega)
          · rw [show blankIndex (TapeSymbol.bit b :: rest) + 1
                  = (blankIndex rest + 1) + 1 by simp [blankIndex]]
            rw [Function.iterate_succ_apply, moveRight_cons_bit]
            exact iheq

/-! ## The scanning macro -/

/-- Move tape `i`'s head one cell right, leaving every other tape alone. -/
def moveRightAction (i : Fin tapes) :
    (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
  fun symbols j => (symbols j, if j = i then HeadMove.right else HeadMove.stay)

/-- "Tape `i`'s head is not on a blank." -/
def notBlankAt (i : Fin tapes) : (Fin tapes → TapeSymbol) → Bool :=
  fun symbols => match symbols i with
    | TapeSymbol.blank => false
    | TapeSymbol.bit _ => true

theorem applyAction_moveRightAction (tape : Fin tapes → Tape) (i : Fin tapes) :
    applyAction tape (moveRightAction i) =
      Function.update tape i (moveRight (tape i)) := by
  funext j
  by_cases hj : j = i
  · subst hj
    simp [applyAction, moveRightAction, moveRight, Tape.write_head_self]
  · simp [applyAction, moveRightAction, hj, Tape.write_head_self, Tape.move]

/-- The loop body: step right, then ask whether we are still on written tape. -/
def scanRightBody (i : Fin tapes) :
    TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
  (TypedMachine.act (moveRightAction i)).andThen
    (fun _ => TypedMachine.test (notBlankAt i))

/-- Advance tape `i`'s head to the first blank at or to the right of the next
cell.  Every other tape is untouched. -/
def scanRightToBlank (i : Fin tapes) :
    TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
  (scanRightBody i).repeatUntilFalse

/-- Tapes after `n` rounds of the scan: tape `i` advanced `n` cells. -/
def scanTapes (tape : Fin tapes → Tape) (i : Fin tapes) (n : Nat) :
    Fin tapes → Tape :=
  Function.update tape i (moveRight^[n] (tape i))

theorem scanTapes_zero (tape : Fin tapes → Tape) (i : Fin tapes) :
    scanTapes tape i 0 = tape := by
  funext j; by_cases hj : j = i <;> simp [scanTapes, hj]

theorem scanTapes_succ (tape : Fin tapes → Tape) (i : Fin tapes) (n : Nat) :
    applyAction (scanTapes tape i n) (moveRightAction i) =
      scanTapes tape i (n + 1) := by
  rw [applyAction_moveRightAction]
  funext j
  by_cases hj : j = i
  · subst hj
    simp [scanTapes, Function.iterate_succ_apply']
  · simp [scanTapes, hj]

/-- One round of the scan costs three steps, advances tape `i` by one cell, and
reports whether to continue. -/
theorem scanRightBody_spec (i : Fin tapes) (tape : Fin tapes → Tape) :
    HaltsExactly (scanRightBody i)
      ((scanRightBody i).startCfg tape) (1 + 1 + 1)
      (notBlankAt i (fun j => ((applyAction tape (moveRightAction i)) j).head)) := by
  have h₂ :
      HaltsExactly (TypedMachine.test (notBlankAt i))
        ((TypedMachine.test (notBlankAt i)).startCfg
          (((TypedMachine.act (moveRightAction i)).step^[1])
            ((TypedMachine.act (moveRightAction i)).startCfg tape)).tape) 1
        (notBlankAt i
          (fun j => ((applyAction tape (moveRightAction i)) j).head)) := by
    rw [TypedMachine.act_tape]
    exact TypedMachine.test_spec (notBlankAt i) _
  exact HaltsExactly.andThen (TypedMachine.act_spec (moveRightAction i) tape) h₂

theorem scanRightBody_tape (i : Fin tapes) (tape : Fin tapes → Tape) :
    (((scanRightBody i).step^[1 + 1 + 1])
        ((scanRightBody i).startCfg tape)).tape =
      applyAction tape (moveRightAction i) := by
  have h := TypedMachine.doWhile_round_tape
    (TypedMachine.act (moveRightAction i)) (notBlankAt i) tape 1 true
    (TypedMachine.act_spec (moveRightAction i) tape).halts
    (TypedMachine.act_spec (moveRightAction i) tape).fresh
  rw [TypedMachine.act_tape] at h
  exact h


/-! ## Generic loop specifications

`repeatUntilFalse_rounds` locates the machine at round boundaries; to feed a
loop into `HaltsExactly.andThen` one also needs that it does not halt in
between.  These three lemmas close that gap once, generically. -/

variable {S : Type}

/-- Strictly before the body halts, the loop has not halted either. -/
theorem TypedMachine.repeatUntilFalse_pre_fresh
    (body : TypedMachine tapes S) (c : TypedConfiguration tapes S)
    (a : Nat) (v : Bool) (h : HaltsExactly body c a v) :
    ∀ t, t < a →
      body.repeatUntilFalse.result
        ((body.repeatUntilFalse.step^[t]) c).state = none := by
  intro t ht
  rw [body.repeatUntilFalse_iterate_fresh c t (fun j hj => h.fresh j (by omega))]
  simp [TypedMachine.repeatUntilFalse, h.fresh t ht]

/-- A round that ends in `true` does not halt the loop: it restarts it. -/
theorem TypedMachine.repeatUntilFalse_round_fresh
    (body : TypedMachine tapes S) (c : TypedConfiguration tapes S)
    (a : Nat) (h : HaltsExactly body c a true) :
    ∀ t, t < a + 1 →
      body.repeatUntilFalse.result
        ((body.repeatUntilFalse.step^[t]) c).state = none := by
  intro t ht
  rcases Nat.lt_or_ge t a with hlt | hge
  · exact body.repeatUntilFalse_pre_fresh c a true h t hlt
  · have hta : t = a := by omega
    subst hta
    rw [body.repeatUntilFalse_iterate_fresh c t h.fresh]
    simp [TypedMachine.repeatUntilFalse, h.halts]

theorem TypedMachine.repeatUntilFalse_rounds_fresh
    (body : TypedMachine tapes S)
    (config : Nat → TypedConfiguration tapes S) (cost : Nat → Nat) (rounds : Nat)
    (hround : ∀ i, i < rounds →
      HaltsExactly body (config i) (cost i) true ∧
        config (i + 1) = ⟨body.start, ((body.step^[cost i]) (config i)).tape⟩) :
    ∀ j, j < loopCost cost rounds →
      body.repeatUntilFalse.result
        ((body.repeatUntilFalse.step^[j]) (config 0)).state = none := by
  induction rounds with
  | zero => intro j hj; simp [loopCost] at hj
  | succ rounds ih =>
      intro j hj
      rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt | hge
      · exact ih (fun i hi => hround i (by omega)) j hlt
      · obtain ⟨t, ht⟩ := Nat.exists_eq_add_of_le hge
        have htlt : t < cost rounds + 1 := by
          rw [loopCost] at hj; omega
        rw [ht, Nat.add_comm, Function.iterate_add_apply,
          body.repeatUntilFalse_rounds config cost rounds
            (fun i hi => hround i (by omega))]
        exact body.repeatUntilFalse_round_fresh (config rounds) (cost rounds)
          (hround rounds (by omega)).1 t htlt

/-- **The loop as a subroutine.**  Given per-round specs and a final round that
reports `false`, the whole loop is a `HaltsExactly` subroutine of cost
`loopCost cost rounds + a` — and therefore composes with `andThen`. -/
theorem TypedMachine.repeatUntilFalse_spec
    (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) :
    HaltsExactly body.repeatUntilFalse (config 0)
      (loopCost cost rounds + a) false := by
  have hrun := body.repeatUntilFalse_rounds config cost rounds hround
  constructor
  · rw [Nat.add_comm, Function.iterate_add_apply, hrun]
    exact body.repeatUntilFalse_exit (config rounds) a hexit
  · intro j hj
    rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt | hge
    · exact body.repeatUntilFalse_rounds_fresh config cost rounds hround j hlt
    · 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 body.repeatUntilFalse_pre_fresh (config rounds) a false hexit t htlt

theorem loopCost_const (c : Nat) :
    ∀ n : Nat, loopCost (fun _ => c) n = n * (c + 1) := by
  intro n
  induction n with
  | zero => simp [loopCost]
  | succ n ih => rw [loopCost, ih, Nat.succ_mul]


/-! ## The scan, specified

Assembling the pieces.  Note that nothing below reasons about `step` or `run`:
the round spec comes from `HaltsExactly.andThen`, the loop spec from
`repeatUntilFalse_spec`, and the tape facts from `blank_scan_spec`. -/

theorem notBlankAt_true (i : Fin tapes) (t : Fin tapes → Tape)
    (h : (t i).head ≠ TapeSymbol.blank) :
    notBlankAt i (fun j => (t j).head) = true := by
  show (match (t i).head with
        | TapeSymbol.blank => false
        | TapeSymbol.bit _ => true) = true
  cases hcase : (t i).head with
  | blank => exact absurd hcase h
  | bit b => rfl

theorem notBlankAt_false (i : Fin tapes) (t : Fin tapes → Tape)
    (h : (t i).head = TapeSymbol.blank) :
    notBlankAt i (fun j => (t j).head) = false := by
  show (match (t i).head with
        | TapeSymbol.blank => false
        | TapeSymbol.bit _ => true) = false
  rw [h]

theorem scanTapes_head (tape : Fin tapes → Tape) (i : Fin tapes) (n : Nat) :
    ((scanTapes tape i n) i).head = (moveRight^[n] (tape i)).head := by
  simp [scanTapes]

/-- Round `m` of the scan continues precisely when cell `m + 1` is written. -/
theorem scanRightBody_round (i : Fin tapes) (tape : Fin tapes → Tape) (m : Nat) :
    HaltsExactly (scanRightBody i)
      ((scanRightBody i).startCfg (scanTapes tape i m)) (1 + 1 + 1)
      (notBlankAt i (fun j => ((scanTapes tape i (m + 1)) j).head)) := by
  have h := scanRightBody_spec i (scanTapes tape i m)
  rwa [scanTapes_succ] at h

theorem scanRightBody_round_tape (i : Fin tapes) (tape : Fin tapes → Tape)
    (m : Nat) :
    (((scanRightBody i).step^[1 + 1 + 1])
        ((scanRightBody i).startCfg (scanTapes tape i m))).tape =
      scanTapes tape i (m + 1) := by
  rw [scanRightBody_tape, scanTapes_succ]

/-- **The scanning macro, specified.**  Starting anywhere, `scanRightToBlank i`
advances tape `i` to the first blank strictly to the right of the head, in
`4 · d + 3` steps where `d` is the distance to that blank.  The step count is a
function of the tape contents, not a numeral — which is exactly what a finite
state space cannot express on its own. -/
theorem scanRightToBlank_spec (i : Fin tapes) (tape : Fin tapes → Tape) :
    HaltsExactly (scanRightToBlank i)
      ((scanRightToBlank i).startCfg tape)
      (blankIndex (tape i).right * 4 + 3) false := by
  set d := blankIndex (tape i).right with hd
  obtain ⟨hlt, heq⟩ :=
    blank_scan_spec (tape i).right (tape i).left (tape i).head
  have htape : (⟨(tape i).left, (tape i).head, (tape i).right⟩ : Tape) = tape i := rfl
  rw [htape] at hlt heq
  have hround : ∀ m, m < d →
      HaltsExactly (scanRightBody i)
          ((scanRightBody i).startCfg (scanTapes tape i m)) (1 + 1 + 1) true ∧
        (scanRightBody i).startCfg (scanTapes tape i (m + 1)) =
          ⟨(scanRightBody i).start,
            (((scanRightBody i).step^[1 + 1 + 1])
              ((scanRightBody i).startCfg (scanTapes tape i m))).tape⟩ := by
    intro m hm
    have hhead : ((scanTapes tape i (m + 1)) i).head ≠ TapeSymbol.blank := by
      rw [scanTapes_head]; exact hlt m hm
    have hverdict :
        notBlankAt i (fun j => ((scanTapes tape i (m + 1)) j).head) = true := by
      exact notBlankAt_true i (scanTapes tape i (m + 1)) hhead
    refine ⟨?_, ?_⟩
    · have h := scanRightBody_round i tape m
      rwa [hverdict] at h
    · rw [scanRightBody_round_tape]
      rfl
  have hexit :
      HaltsExactly (scanRightBody i)
        ((scanRightBody i).startCfg (scanTapes tape i d)) (1 + 1 + 1) false := by
    have hhead : ((scanTapes tape i (d + 1)) i).head = TapeSymbol.blank := by
      rw [scanTapes_head]; exact heq
    have hverdict :
        notBlankAt i (fun j => ((scanTapes tape i (d + 1)) j).head) = false := by
      exact notBlankAt_false i (scanTapes tape i (d + 1)) hhead
    have h := scanRightBody_round i tape d
    rwa [hverdict] at h
  have hloop :=
    TypedMachine.repeatUntilFalse_spec (scanRightBody i)
      (fun m => (scanRightBody i).startCfg (scanTapes tape i m))
      (fun _ => 1 + 1 + 1) d (1 + 1 + 1) hround hexit
  rw [loopCost_const] at hloop
  simp only [scanTapes_zero] at hloop
  exact hloop

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_machine_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