Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Erasing a contiguous run

Definition
sgl_erase_run

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Erasing a contiguous run. eraseRun i walks tape i rightwards over a run of non-blank cells, blanking each: mmm marks in 5m+45m + 45m+4 steps, head left on the blank past the run. It is the guided walk with one tape playing both roles, and it is what retires a clock once its marks have been spent.

With guidedWalk this completes the erase toolkit. A clock of TTT marks drives the worker's head 2T2T2T right and then 4T4T4T left writing blanks — covering every cell a TTT-step run could have written, since each head moves at most one cell per step — after which this machine erases the clock, leaving both tapes blank for the next round.

The last three lemmas are what make it usable: for a tape presented as cellsTape L (marks ++ blank :: R) with marks non-blank, eraseRun_spec's hypotheses are read straight off the list, and the result is the marks replaced by blanks in the left context. A caller never reasons about the iteration.

Definition code
import Definitions.Def_sgl_guided_walk

/-!
# Erasing a contiguous run

`eraseRun i` walks tape `i` rightwards over a run of non-blank cells, blanking
each.  It is the guided walk with one tape playing both roles, and it is what
retires a clock once its marks have been spent.

Together with `guidedWalk` this completes the erase toolkit: a clock of `T`
marks drives the worker's head `2T` right and then `4T` left writing blanks —
covering every cell a `T`-step run could have written — after which the clock
itself is erased by this machine, leaving both tapes blank for the next round.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-- Blank the current cell and step right. -/
def eraseAction (i : Fin tapes) :
    (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
  fun symbols j =>
    if j = i then (TapeSymbol.blank, HeadMove.right)
    else (symbols j, HeadMove.stay)

/-- One round: test, then blank-and-advance or stop. -/
def eraseBody (i : Fin tapes) :=
  (TypedMachine.test (notBlankAt i)).andThen fun b =>
    if b then
      (TypedMachine.act (eraseAction i)).andThen fun _ =>
        TypedMachine.halt (tapes := tapes) true
    else
      (TypedMachine.act (fun symbols j => (symbols j, HeadMove.stay))).andThen
        fun _ => TypedMachine.halt (tapes := tapes) false

/-- Erase a run of marks. -/
def eraseRun (i : Fin tapes) := (eraseBody i).repeatUntilFalse

/-- The tapes after one erasing round. -/
def eraseStep (i : Fin tapes) (T : Fin tapes → Tape) : Fin tapes → Tape :=
  fun j =>
    if j = i then moveDir HeadMove.right (Tape.write (T i) TapeSymbol.blank)
    else T j

theorem eraseStep_eq (i : Fin tapes) (T : Fin tapes → Tape) :
    applyAction T (eraseAction i) = eraseStep i T := by
  funext j
  show applyAction T (eraseAction i) j =
    (if j = i then moveDir HeadMove.right (Tape.write (T i) TapeSymbol.blank)
      else T j)
  by_cases hj : j = i
  · subst hj
    simp [applyAction, eraseAction, moveDir]
  · simp [applyAction, eraseAction, hj, Tape.write_head_self, Tape.move]


/-! ## Rounds -/

set_option maxHeartbeats 1000000 in
theorem eraseBody_mark (i : Fin tapes) (T : Fin tapes → Tape)
    (hmark : (T i).head ≠ TapeSymbol.blank) :
    HaltsExactly (eraseBody i) ((eraseBody i).startCfg T)
      (1 + 1 + (1 + 1 + 0)) true ∧
    (((eraseBody i).step^[1 + 1 + (1 + 1 + 0)])
      ((eraseBody i).startCfg T)).tape = eraseStep i T := by
  have htest := TypedMachine.test_spec (notBlankAt i) T
  rw [notBlankAt_true i T hmark] at htest
  have htestt : (((TypedMachine.test (notBlankAt i)).step^[1])
      ((TypedMachine.test (notBlankAt i)).startCfg T)).tape = T := by
    rw [Function.iterate_one]
    funext j
    simp [TypedMachine.step, TypedMachine.test, TypedMachine.startCfg,
      Tape.write_head_self, Tape.move]
  have hact := TypedMachine.act_spec (eraseAction i) T
  have hactt : (((TypedMachine.act (eraseAction i)).step^[1])
      ((TypedMachine.act (eraseAction i)).startCfg T)).tape = eraseStep i T := by
    rw [Function.iterate_one, ← eraseStep_eq i]
    funext j
    simp [TypedMachine.step, TypedMachine.act, TypedMachine.startCfg,
      applyAction]
  have hhalt := TypedMachine.halt_spec (tapes := tapes) true
    ((TypedMachine.halt (tapes := tapes) true).startCfg (eraseStep i T))
  have hinner := chainStepC hact hactt hhalt
  have hmain := chainStepD
    (M₂ := fun b =>
      if b then
        (TypedMachine.act (eraseAction i)).andThen fun _ =>
          TypedMachine.halt (tapes := tapes) true
      else
        (TypedMachine.act (fun symbols j => (symbols j, HeadMove.stay))).andThen
          fun _ => TypedMachine.halt (tapes := tapes) false)
    htest htestt (by simpa using hinner.1)
  refine ⟨hmain.1, ?_⟩
  have hfin := hmain.2
  have hfin' : ((eraseBody i).step^[1 + 1 + (1 + 1 + 0)])
      ((eraseBody i).startCfg T) = _ := hfin
  rw [hfin']
  simp only [if_true]
  rw [hinner.2]
  rfl

set_option maxHeartbeats 1000000 in
theorem eraseBody_blank (i : Fin tapes) (T : Fin tapes → Tape)
    (hblank : (T i).head = TapeSymbol.blank) :
    HaltsExactly (eraseBody i) ((eraseBody i).startCfg T)
      (1 + 1 + (1 + 1 + 0)) false ∧
    (((eraseBody i).step^[1 + 1 + (1 + 1 + 0)])
      ((eraseBody i).startCfg T)).tape = T := by
  have htest := TypedMachine.test_spec (notBlankAt i) T
  rw [notBlankAt_false i T hblank] at htest
  have htestt : (((TypedMachine.test (notBlankAt i)).step^[1])
      ((TypedMachine.test (notBlankAt i)).startCfg T)).tape = T := by
    rw [Function.iterate_one]
    funext j
    simp [TypedMachine.step, TypedMachine.test, TypedMachine.startCfg,
      Tape.write_head_self, Tape.move]
  have hact := TypedMachine.act_spec
    (fun symbols : Fin tapes → TapeSymbol => fun j =>
      (symbols j, HeadMove.stay)) T
  have hactt : (((TypedMachine.act
      (fun symbols : Fin tapes → TapeSymbol => fun j =>
        (symbols j, HeadMove.stay))).step^[1])
      ((TypedMachine.act
        (fun symbols : Fin tapes → TapeSymbol => fun j =>
          (symbols j, HeadMove.stay))).startCfg T)).tape = T := by
    rw [Function.iterate_one]
    funext j
    simp [TypedMachine.step, TypedMachine.act, TypedMachine.startCfg,
      applyAction, Tape.write_head_self, Tape.move]
  have hhalt := TypedMachine.halt_spec (tapes := tapes) false
    ((TypedMachine.halt (tapes := tapes) false).startCfg T)
  have hinner := chainStepC hact hactt hhalt
  have hmain := chainStepD
    (M₂ := fun b =>
      if b then
        (TypedMachine.act (eraseAction i)).andThen fun _ =>
          TypedMachine.halt (tapes := tapes) true
      else
        (TypedMachine.act (fun symbols j => (symbols j, HeadMove.stay))).andThen
          fun _ => TypedMachine.halt (tapes := tapes) false)
    htest htestt (by simpa using hinner.1)
  refine ⟨hmain.1, ?_⟩
  have hfin := hmain.2
  have hfin' : ((eraseBody i).step^[1 + 1 + (1 + 1 + 0)])
      ((eraseBody i).startCfg T) = _ := hfin
  rw [hfin']
  simp only [Bool.false_eq_true, if_false]
  rw [hinner.2]
  rfl

set_option maxHeartbeats 1000000 in
/-- **Erasing a run.**  A run of `m` marks is blanked in `5m + 4` steps, the
head left on the blank past it. -/
theorem eraseRun_spec (i : Fin tapes) (m : Nat) (T : Fin tapes → Tape)
    (hmarks : ∀ r, r < m → ((((eraseStep i)^[r]) T) i).head ≠ TapeSymbol.blank)
    (hexit : ((((eraseStep i)^[m]) T) i).head = TapeSymbol.blank) :
    HaltsExactly (eraseRun i) ((eraseRun i).startCfg T) (m * 5 + 4) false ∧
    (((eraseRun i).step^[m * 5 + 4]) ((eraseRun i).startCfg T)).tape =
      ((eraseStep i)^[m]) T := by
  classical
  set body := eraseBody i with hbody
  set cfg : Nat → TypedConfiguration tapes _ :=
    fun r => body.startCfg (((eraseStep i)^[r]) T) with hcfg
  have hround : ∀ r, r < m →
      HaltsExactly body (cfg r) 4 true ∧
        cfg (r + 1) = ⟨body.start, ((body.step^[4]) (cfg r)).tape⟩ := by
    intro r hr
    obtain ⟨hh, ht⟩ := eraseBody_mark i (((eraseStep i)^[r]) T) (hmarks r hr)
    have hh4 : HaltsExactly body (cfg r) 4 true := by
      rw [hcfg, hbody]; simpa using hh
    have ht4 : ((body.step^[4]) (cfg r)).tape = ((eraseStep i)^[r + 1]) T := by
      rw [hcfg, hbody]
      rw [show (4 : Nat) = 1 + 1 + (1 + 1 + 0) from rfl]
      rw [ht, Function.iterate_succ_apply']
    refine ⟨hh4, ?_⟩
    show body.startCfg (((eraseStep i)^[r + 1]) T) = _
    rw [← ht4]
    rfl
  have hexitr : HaltsExactly body (cfg m) 4 false := by
    have := (eraseBody_blank i (((eraseStep i)^[m]) T) hexit).1
    rw [hcfg, hbody]; simpa using this
  have hspec := TypedMachine.repeatUntilFalse_spec body cfg (fun _ => 4) m 4
    hround hexitr
  rw [loopCost_const] at hspec
  have hrun := TypedMachine.repeatUntilFalse_rounds body cfg (fun _ => 4) m
    hround
  rw [loopCost_const] at hrun
  have hstart : (eraseRun i).startCfg T = cfg 0 := by rw [hcfg]; rfl
  refine ⟨by rw [hstart]; simpa using hspec, ?_⟩
  rw [hstart, show m * 5 + 4 = 4 + m * (4 + 1) by omega,
    Function.iterate_add_apply]
  show ((eraseRun i).step^[4]
    (((eraseRun i).step^[m * (4 + 1)]) (cfg 0))).tape = _
  rw [show (eraseRun i) = body.repeatUntilFalse from rfl, hrun]
  have htp : ((body.repeatUntilFalse.step^[4]) (cfg m)).tape =
      ((body.step^[4]) (cfg m)).tape := by
    rw [body.repeatUntilFalse_iterate_fresh (cfg m) 4 hexitr.fresh]
  rw [htp, hcfg, hbody]
  exact (eraseBody_blank i (((eraseStep i)^[m]) T) hexit).2


/-! ## Applying it to a concrete run

For a tape presented as `cellsTape L (marks ++ blank :: R)` with `marks`
non-blank, the hypotheses of `eraseRun_spec` are read off the list.
-/

theorem eraseStep_cellsTape (i : Fin tapes) (T : Fin tapes → Tape)
    (L R : List TapeSymbol) (c : TapeSymbol)
    (hT : T i = cellsTape L (c :: R)) :
    (eraseStep i T) i = cellsTape (TapeSymbol.blank :: L) R := by
  show (if i = i then moveDir HeadMove.right
    (Tape.write (T i) TapeSymbol.blank) else T i) = _
  rw [if_pos rfl, hT, write_cellsTape]
  show moveDir HeadMove.right (cellsTape L (TapeSymbol.blank :: R)) = _
  rw [cellsTape_moveRight]

theorem replicate_cons_comm (n : Nat) (b : TapeSymbol) (L : List TapeSymbol) :
    List.replicate n b ++ (b :: L) = b :: (List.replicate n b ++ L) := by
  induction n with
  | zero => rfl
  | succ n ih => rw [List.replicate_succ, List.cons_append, ih]; rfl

/-- Iterating the erase over a run of marks. -/
theorem eraseStep_iterate (i : Fin tapes) :
    ∀ (marks : List TapeSymbol) (T : Fin tapes → Tape) (L R : List TapeSymbol),
      T i = cellsTape L (marks ++ R) →
      ((((eraseStep i)^[marks.length]) T) i) =
        cellsTape (List.replicate marks.length TapeSymbol.blank ++ L) R := by
  intro marks
  induction marks with
  | nil => intro T L R hT; simpa using hT
  | cons c marks ih =>
      intro T L R hT
      rw [List.length_cons, Function.iterate_succ_apply]
      have hstep : (eraseStep i T) i =
          cellsTape (TapeSymbol.blank :: L) (marks ++ R) := by
        exact eraseStep_cellsTape i T L (marks ++ R) c (by rw [hT]; rfl)
      rw [ih (eraseStep i T) (TapeSymbol.blank :: L) R hstep]
      congr 1
      exact replicate_cons_comm marks.length TapeSymbol.blank L

/-- Every cell of the run is seen before the blank. -/
theorem eraseStep_marks (i : Fin tapes) :
    ∀ (marks : List TapeSymbol) (T : Fin tapes → Tape) (L R : List TapeSymbol),
      (∀ c ∈ marks, c ≠ TapeSymbol.blank) →
      T i = cellsTape L (marks ++ R) →
      ∀ r, r < marks.length →
        ((((eraseStep i)^[r]) T) i).head ≠ TapeSymbol.blank := by
  intro marks
  induction marks with
  | nil => intro _ _ _ _ _ r hr; simp at hr
  | cons c marks ih =>
      intro T L R hnb hT r hr
      cases r with
      | zero =>
          simp only [Function.iterate_zero, id_eq]
          rw [hT]
          show (cellsTape L (c :: (marks ++ R))).head ≠ _
          exact hnb c (by simp)
      | succ r' =>
          rw [Function.iterate_succ_apply]
          have hstep : (eraseStep i T) i =
              cellsTape (TapeSymbol.blank :: L) (marks ++ R) :=
            eraseStep_cellsTape i T L (marks ++ R) c (by rw [hT]; rfl)
          exact ih (eraseStep i T) (TapeSymbol.blank :: L) R
            (fun x hx => hnb x (by simp [hx])) hstep r'
            (by simp at hr; omega)

end SipserGacsLautemann
Source
Erase primitive completing the I0 toolkit; builds on Def_sgl_guided_walk.

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