Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Walking the region to a flag

Definition
sgl_region_walk

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Walking the region to a flag: the sweep loop, fully specified.

walkToFlag repeats blockRead until the block whose track-flag is set has been consumed. Its specification is exact on all three axes: the machine halts false at precisely 13∣mid∣+1213|{\rm mid}|+1213∣mid∣+12 steps (where mid is the unflagged prefix), the final configuration equals the last body run's — so the exit state carries the flagged block's cells, which the read phases of the simulation will extract — and the tapes are unchanged except tape iii, whose head stands just past the flagged block.

The cellsTape view. Tape is a zipper, and a zipper remembers where the head has been: moving onto the blank beyond the region and back leaves a visited blank in the lists, so the tape is no longer structurally equal to its clean description. This bites exactly when the flagged block is last, and it would otherwise have surfaced as an unprovable goal deep inside the update sweep. cellsTape L R — head reading the first cell of R, blank if R is empty — makes the bookkeeping uniform: every head move is a list shuffle provable by rfl after a case split, and a visited blank is a [blank] suffix carried in R. The identity cellsTape L [] = cellsTape L [\mathrm{blank}] holds definitionally, so the first excursion beyond the region costs nothing.

Structure of the proof. The walk is repeatUntilFalse over blockRead; each round's verdict comes from blockOfCells_cellsTape (the block standing at boundary mmm is mid[m], whose flag is down), each round's tape effect from blockRead_tape (six cells of advance, nothing else touched), and the boundary bookkeeping from one rewrite chain over take/drop splits — no bespoke induction. Also here: repeatUntilFalse_config, the full-configuration form of the loop run lemmas, which downstream phases need because a loop's exit state carries the data its last body run collected.

Definition code
import Definitions.Def_sgl_block_read

/-!
# Walking the region to a flag

Module D of the merge_empty plan, second part: the sweep loop.  `walkToFlag`
repeats `blockRead` until it stands past the block whose track-flag is set, and
its specification locates the halt exactly and gives the final tapes.

## The `cellsTape` view

`Tape` is a zipper, and a zipper remembers where the head has been: moving onto
the blank beyond the region and back leaves a *visited* blank in the lists,
so the tape is no longer structurally equal to its clean description.  This
bites precisely when the flagged block is last, and it would have surfaced as
an unprovable goal deep inside the update sweep.

`cellsTape L R` — head reading the first cell of `R`, blank if `R` is empty —
makes the bookkeeping uniform: every head move is a list shuffle, provable by
`rfl` after a case split, and a trailing visited blank is just a `[blank]`
suffix carried in `R`.  Usefully, `cellsTape L [] = cellsTape L [blank]` holds
*definitionally*, so the first excursion beyond the region costs nothing at
all.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-! ## Track sides -/

/-- Which of the two hosted virtual tapes an operation concerns. -/
inductive TrackSide where
  | A
  | B

def TrackSide.getFlag : TrackSide → Block → Bool
  | .A => Block.flagA
  | .B => Block.flagB

/-! ## The `cellsTape` view of a physical tape -/

/-- A tape as: cells left of the head (nearest-first), and cells at and right
of the head.  The head reads the first right-cell, blank if there is none —
the zipper's implicit blank-extension made explicit. -/
def cellsTape (L R : List TapeSymbol) : Tape :=
  ⟨L, R.headD TapeSymbol.blank, R.tail⟩

theorem cellsTape_moveRight (L : List TapeSymbol) (c : TapeSymbol)
    (R : List TapeSymbol) :
    moveDir HeadMove.right (cellsTape L (c :: R)) = cellsTape (c :: L) R := by
  cases R <;> rfl

theorem cellsTape_moveRight_nil (L : List TapeSymbol) :
    moveDir HeadMove.right (cellsTape L []) =
      cellsTape (TapeSymbol.blank :: L) [] := rfl

theorem cellsTape_moveLeft (L : List TapeSymbol) (c r : TapeSymbol)
    (R : List TapeSymbol) :
    moveDir HeadMove.left (cellsTape (c :: L) (r :: R)) =
      cellsTape L (c :: r :: R) := rfl

theorem cellsTape_moveLeft_nil (L : List TapeSymbol) (c : TapeSymbol) :
    moveDir HeadMove.left (cellsTape (c :: L) []) =
      cellsTape L (c :: [TapeSymbol.blank]) := rfl

/-- Consuming a run of cells rightward. -/
theorem cellsTape_advance (cs : List TapeSymbol) :
    ∀ (L R : List TapeSymbol),
      (moveDir HeadMove.right)^[cs.length] (cellsTape L (cs ++ R)) =
        cellsTape (cs.reverse ++ L) R := by
  induction cs with
  | nil => intro L R; simp
  | cons c cs ih =>
      intro L R
      rw [List.length_cons, Function.iterate_succ_apply, List.cons_append,
        cellsTape_moveRight, ih]
      simp [List.append_assoc]

/-- Retreating over a run of cells leftward, with something ahead. -/
theorem cellsTape_retreat (cs : List TapeSymbol) :
    ∀ (L R : List TapeSymbol) (r : TapeSymbol),
      (moveDir HeadMove.left)^[cs.length] (cellsTape (cs ++ L) (r :: R)) =
        cellsTape L (cs.reverse ++ r :: R) := by
  induction cs with
  | nil => intro L R r; simp
  | cons c cs ih =>
      intro L R r
      rw [List.length_cons, Function.iterate_succ_apply, List.cons_append,
        cellsTape_moveLeft, ih]
      simp [List.append_assoc]

/-- Retreating from the position just past the region: the first step
materialises the visited blank, and it lands at the run's start with that
blank recorded ahead. -/
theorem cellsTape_retreat_end (cs : List TapeSymbol) (L : List TapeSymbol) :
    (moveDir HeadMove.left)^[cs.length] (cellsTape (cs ++ L) []) =
      cellsTape L (cs.reverse ++ [TapeSymbol.blank]) := by
  cases cs with
  | nil => rfl
  | cons c cs =>
      rw [List.length_cons, Function.iterate_succ_apply, List.cons_append,
        cellsTape_moveLeft_nil, cellsTape_retreat]
      simp

/-! ## Splitting an encoded region -/

theorem encodeBlocks_append (xs ys : List Block) :
    encodeBlocks (xs ++ ys) = encodeBlocks xs ++ encodeBlocks ys := by
  induction xs with
  | nil => rfl
  | cons b bs ih => simp [encodeBlocks_cons, ih]

/-- The block a head standing at a boundary is looking at, recovered from the
cells: the `cellsTape` version of the codec/reader join. -/
theorem blockOfCells_cellsTape (i : Fin tapes) (tape : Fin tapes → Tape)
    (L R : List TapeSymbol) (b : Block)
    (hi : tape i = cellsTape L (Block.toCells b ++ R)) :
    blockOfCells (cellAt i tape 0) (cellAt i tape 1) (cellAt i tape 2)
      (cellAt i tape 3) (cellAt i tape 4) (cellAt i tape 5) = b := by
  have e0 : cellAt i tape 0 = (cellsOfSymbol b.symA).1 := by
    rw [cellAt, hi]; rfl
  have e1 : cellAt i tape 1 = (cellsOfSymbol b.symA).2 := by
    rw [cellAt, hi]; rfl
  have e2 : cellAt i tape 2 = TapeSymbol.bit b.flagA := by
    rw [cellAt, hi]; rfl
  have e3 : cellAt i tape 3 = (cellsOfSymbol b.symB).1 := by
    rw [cellAt, hi]; rfl
  have e4 : cellAt i tape 4 = (cellsOfSymbol b.symB).2 := by
    rw [cellAt, hi]; rfl
  have e5 : cellAt i tape 5 = TapeSymbol.bit b.flagB := by
    rw [cellAt, hi]; rfl
  rw [e0, e1, e2, e3, e4, e5]
  exact blockOfCells_toCells b

/-! ## The tape-effect of a block read -/

/-- `scanTapesDir` at the updated index. -/
theorem scanTapesDir_self (tape : Fin tapes → Tape) (i : Fin tapes)
    (dir : HeadMove) (n : Nat) :
    (scanTapesDir tape i dir n) i = (moveDir dir)^[n] (tape i) := by
  simp [scanTapesDir]

/-- Composing two head-advances of the same tape. -/
theorem scanTapesDir_compose (tape : Fin tapes → Tape) (i : Fin tapes)
    (dir : HeadMove) (n m : Nat) :
    scanTapesDir (scanTapesDir tape i dir n) i dir m =
      scanTapesDir tape i dir (m + n) := by
  funext j
  by_cases hj : j = i
  · subst hj
    simp [scanTapesDir, Function.iterate_add_apply]
  · simp [scanTapesDir, hj]

/-- The tape version of `readCellRight_chain`: one link of the chain, tracking
tapes instead of the verdict. -/
theorem readCellRight_chain_tape {S : Type} (i : Fin tapes)
    (tape : Fin tapes → Tape) (n : Nat)
    (M₂ : Option TapeSymbol → TypedMachine tapes S) (k : Nat)
    (T : Fin tapes → Tape)
    (h : (((M₂ (some (cellAt i tape n))).step^[k])
      ((M₂ (some (cellAt i tape n))).startCfg
        (scanTapesDir tape i HeadMove.right (n + 1)))).tape = T) :
    ((((readCellRight i).andThenState (fun s => s.isSome) M₂).step^[1 + 1 + k])
      (TypedConfiguration.inLeftState
        ((readCellRight i).startCfg
          (scanTapesDir tape i HeadMove.right n)))).tape = T := by
  have hexit : (fun s : Option TapeSymbol => s.isSome)
      (((readCellRight i).step^[1])
        ((readCellRight i).startCfg
          (scanTapesDir tape i HeadMove.right n))).state = true := by
    rw [readCellRight_state]; rfl
  have hfresh : ∀ j, j < 1 →
      (fun s : Option TapeSymbol => s.isSome)
        (((readCellRight i).step^[j])
          ((readCellRight i).startCfg
            (scanTapesDir tape i HeadMove.right n))).state = false := by
    intro j hj
    have : j = 0 := by omega
    subst this; rfl
  rw [TypedMachine.andThenState_iterate _ _ _ _ 1 hexit hfresh k]
  simp only [TypedConfiguration.inRightState]
  rw [readCellRight_state, readCellRight_tape, advance_succ, advance_head] at *
  exact h

/-- The first link, on the original tapes. -/
theorem readCellRight_chain_tape_zero {S : Type} (i : Fin tapes)
    (tape : Fin tapes → Tape)
    (M₂ : Option TapeSymbol → TypedMachine tapes S) (k : Nat)
    (T : Fin tapes → Tape)
    (h : (((M₂ (some (cellAt i tape 0))).step^[k])
      ((M₂ (some (cellAt i tape 0))).startCfg
        (scanTapesDir tape i HeadMove.right 1))).tape = T) :
    ((((readCellRight i).andThenState (fun s => s.isSome) M₂).step^[1 + 1 + k])
      (TypedConfiguration.inLeftState ((readCellRight i).startCfg tape))).tape
      = T := by
  have hc := readCellRight_chain_tape i tape 0 M₂ k T h
  rwa [scanTapesDir_zero] at hc

/-- The number of steps of one `blockRead`. -/
def blockReadSteps : Nat :=
  1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + 0)))))

/-- A block read advances tape `i` by exactly six cells and touches nothing
else. -/
theorem blockRead_tape (i : Fin tapes) (test : Block → Bool)
    (tape : Fin tapes → Tape) :
    (((blockRead i test).step^[blockReadSteps])
      (TypedConfiguration.inLeftState
        ((readCellRight i).startCfg tape))).tape =
      scanTapesDir tape i HeadMove.right 6 := by
  refine readCellRight_chain_tape_zero i tape _ _ _ ?_
  refine readCellRight_chain_tape i tape 1 _ _ _ ?_
  refine readCellRight_chain_tape i tape 2 _ _ _ ?_
  refine readCellRight_chain_tape i tape 3 _ _ _ ?_
  refine readCellRight_chain_tape i tape 4 _ _ _ ?_
  refine readCellRight_chain_tape i tape 5 _ _ _ ?_
  rfl

/-- The full final configuration of a `repeatUntilFalse` run — state and tapes
together.  `repeatUntilFalse_spec` gives the verdict and `repeatUntilFalse_tape`
the tapes; downstream phases also need the *state*, because a loop's exit state
carries the data its last body run collected. -/
theorem TypedMachine.repeatUntilFalse_config {S : Type}
    (body : TypedMachine tapes S)
    (config : Nat → TypedConfiguration tapes S) (cost : Nat → Nat)
    (rounds 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)) =
      (body.step^[a]) (config rounds) := 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]

/-! ## The walk -/

/-- Continue while the current block's `side` flag is down. -/
def walkTest (side : TrackSide) : Block → Bool :=
  fun b => !side.getFlag b

def walkBody (side : TrackSide) (i : Fin tapes) :=
  blockRead i (walkTest side)

/-- Repeat block reads until the flagged block has been consumed. -/
def walkToFlag (side : TrackSide) (i : Fin tapes) :=
  (walkBody side i).repeatUntilFalse

/-- The tape at boundary `m` of the walk, in region terms. -/
theorem walk_boundary (L R : List TapeSymbol) (mid : List Block) (cur : Block)
    (post : List Block) (m : Nat) (hm : m < mid.length) :
    (moveDir HeadMove.right)^[6 * m]
        (cellsTape L (encodeBlocks (mid ++ cur :: post) ++ R)) =
      cellsTape ((encodeBlocks (mid.take m)).reverse ++ L)
        (Block.toCells (mid.getD m Block.blank) ++
          (encodeBlocks (mid.drop (m + 1) ++ cur :: post) ++ R)) := by
  conv_lhs =>
    rw [show mid ++ cur :: post = mid.take m ++ (mid.drop m ++ cur :: post) by
      rw [← List.append_assoc, List.take_append_drop]]
  rw [show mid.drop m = mid.getD m Block.blank :: mid.drop (m + 1) by
    rw [List.getD_eq_getElem mid Block.blank hm]
    exact List.drop_eq_getElem_cons hm]
  rw [encodeBlocks_append, List.cons_append, encodeBlocks_cons]
  simp only [List.append_assoc]
  rw [show (6 : Nat) * m = (encodeBlocks (mid.take m)).length by
    rw [encodeBlocks_length, List.length_take]; omega,
    cellsTape_advance]

/-- The tape at the flagged block's boundary. -/
theorem walk_boundary_cur (L R : List TapeSymbol) (mid : List Block)
    (cur : Block) (post : List Block) :
    (moveDir HeadMove.right)^[6 * mid.length]
        (cellsTape L (encodeBlocks (mid ++ cur :: post) ++ R)) =
      cellsTape ((encodeBlocks mid).reverse ++ L)
        (Block.toCells cur ++ (encodeBlocks post ++ R)) := by
  rw [encodeBlocks_append, encodeBlocks_cons, List.append_assoc,
    List.append_assoc,
    show (6 : Nat) * mid.length = (encodeBlocks mid).length by
      rw [encodeBlocks_length],
    cellsTape_advance]

/-- **The walk, specified.**  From a region `mid ++ cur :: post` whose `side`
flag is down throughout `mid` and up at `cur`, the walk halts `false` after
`|mid|` full rounds plus the read of `cur`, leaving every tape unchanged except
tape `i`, whose head has advanced past `cur`. -/
theorem walkToFlag_spec (side : TrackSide) (i : Fin tapes)
    (tape : Fin tapes → Tape) (L R : List TapeSymbol)
    (mid : List Block) (cur : Block) (post : List Block)
    (hmid : ∀ b ∈ mid, side.getFlag b = false)
    (hcur : side.getFlag cur = true)
    (hi : tape i = cellsTape L (encodeBlocks (mid ++ cur :: post) ++ R)) :
    HaltsExactly (walkToFlag side i) ((walkToFlag side i).startCfg tape)
      (loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps) false ∧
    ((walkToFlag side i).step^[
        loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps])
      ((walkToFlag side i).startCfg tape) =
      (walkBody side i).step^[blockReadSteps]
        ⟨(walkBody side i).start,
          scanTapesDir tape i HeadMove.right (6 * mid.length)⟩ ∧
    (((walkToFlag side i).step^[
        loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps])
      ((walkToFlag side i).startCfg tape)).tape =
      scanTapesDir tape i HeadMove.right (6 * (mid.length + 1)) := by
  set body := walkBody side i with hbody
  -- the round plan: tapes advanced by 6m cells
  set T : Nat → (Fin tapes → Tape) :=
    fun m => scanTapesDir tape i HeadMove.right (6 * m) with hT
  set config : Nat → TypedConfiguration tapes _ :=
    fun m => ⟨body.start, T m⟩ with hconfig
  -- each round's tape effect
  have htapeStep : ∀ m : Nat,
      ((body.step^[blockReadSteps]) (config m)).tape = T (m + 1) := by
    intro m
    have hc : config m =
        TypedConfiguration.inLeftState ((readCellRight i).startCfg (T m)) := rfl
    rw [hc, hbody]
    show (((blockRead i (walkTest side)).step^[blockReadSteps])
      (TypedConfiguration.inLeftState
        ((readCellRight i).startCfg (T m)))).tape = T (m + 1)
    rw [blockRead_tape]
    simp only [hT]
    rw [scanTapesDir_compose, show 6 + 6 * m = 6 * (m + 1) by omega]
  -- each round's verdict, from whatever block stands at the boundary
  have hverdict : ∀ (m : Nat) (b : Block) (L' R' : List TapeSymbol),
      T m i = cellsTape L' (Block.toCells b ++ R') →
      HaltsExactly body (config m) blockReadSteps (walkTest side b) := by
    intro m b L' R' hTi
    have hb := blockOfCells_cellsTape i (T m) L' R' b hTi
    have hs := blockRead_spec i (walkTest side) (T m)
    rw [hb] at hs
    exact hs
  have hround : ∀ m, m < mid.length →
      HaltsExactly body (config m) blockReadSteps true ∧
        config (m + 1) =
          ⟨body.start, ((body.step^[blockReadSteps]) (config m)).tape⟩ := by
    intro m hm
    have hTi : T m i = cellsTape ((encodeBlocks (mid.take m)).reverse ++ L)
        (Block.toCells (mid.getD m Block.blank) ++
          (encodeBlocks (mid.drop (m + 1) ++ cur :: post) ++ R)) := by
      rw [hT]
      simp only [scanTapesDir_self]
      rw [hi]
      exact walk_boundary L R mid cur post m hm
    have h := hverdict m (mid.getD m Block.blank) _ _ hTi
    have hflag : walkTest side (mid.getD m Block.blank) = true := by
      have hmem : mid.getD m Block.blank ∈ mid := by
        rw [List.getD_eq_getElem mid Block.blank hm]
        exact List.getElem_mem hm
      rw [walkTest, hmid _ hmem]
      rfl
    rw [hflag] at h
    refine ⟨h, ?_⟩
    rw [htapeStep m]
  have hexit : HaltsExactly body (config mid.length) blockReadSteps false := by
    have hTi : T mid.length i =
        cellsTape ((encodeBlocks mid).reverse ++ L)
          (Block.toCells cur ++ (encodeBlocks post ++ R)) := by
      rw [hT]
      simp only [scanTapesDir_self]
      rw [hi]
      exact walk_boundary_cur L R mid cur post
    have h := hverdict mid.length cur _ _ hTi
    have hflag : walkTest side cur = false := by
      rw [walkTest, hcur]
      rfl
    rwa [hflag] at h
  -- assemble
  have hmain := TypedMachine.repeatUntilFalse_spec body config
    (fun _ => blockReadSteps) mid.length blockReadSteps hround hexit
  have hcfgF := TypedMachine.repeatUntilFalse_config body config
    (fun _ => blockReadSteps) mid.length blockReadSteps hround hexit
  have htape := TypedMachine.repeatUntilFalse_tape body config
    (fun _ => blockReadSteps) mid.length blockReadSteps hround hexit
  have hcfg0 : config 0 = (walkToFlag side i).startCfg tape := by
    rw [hconfig]
    show (⟨body.start, T 0⟩ : TypedConfiguration tapes _) = _
    rw [hT]
    show (⟨body.start, scanTapesDir tape i HeadMove.right (6 * 0)⟩ :
      TypedConfiguration tapes _) = _
    rw [Nat.mul_zero, scanTapesDir_zero]
    rfl
  rw [hcfg0] at hmain hcfgF htape
  refine ⟨hmain, ?_, ?_⟩
  · show (body.repeatUntilFalse.step^[
        loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps])
      ((walkToFlag side i).startCfg tape) = _
    exact hcfgF
  · show ((body.repeatUntilFalse.step^[
        loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps])
      ((walkToFlag side i).startCfg tape)).tape = _
    rw [htape, htapeStep mid.length]

end SipserGacsLautemann
Source
Standard block-scanning simulation for multitape Turing machines, specialized to the model of Def_sipser_gacs_lautemann; builds on Def_sgl_block_read.

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