Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Advancing past a delegated run's garbage

Definition
sgl_skip_ahead

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Advancing past a delegated run's garbage — instead of erasing it.

After a delegated run the working tapes hold garbage of unknown extent. The obvious remedy is a clock-guided erase, but that costs six clock passes per tape and writes to every cell.

There is a cheaper move, and it comes from what a Turing machine cannot do: tell where on its tape it is. A round therefore does not need clean tapes, only fresh ones. Advance each working tape past everything the previous round could have written, and the region ahead is untouched by construction. Two clock passes per tape, no writing at all, and the correctness argument is the same geometry as the erase — a run of TTT steps moves a head at most TTT cells from its origin, so 2T2T2T to the right of where it stopped is beyond every cell it wrote.

A formalisation note that shaped the statement. The worker's position after mmm advances is given as (moveDir right)[m](\mathrm{moveDir\ right})^{[m]}(moveDir right)[m] applied to its tape, not as list surgery on a cellsTape — because moving right off the end of the written region materialises blanks, so the list form is simply false when the context runs out. That case is exactly the one this machine spends its whole time in.

Definition code
import Definitions.Def_sgl_mark_back

/-!
# Advancing past a delegated run's garbage

After a delegated run the working tapes hold garbage of unknown extent.  The
obvious remedy is to erase it, guided by the clock — but erasing costs six
clock passes per tape and writes to every cell.

There is a cheaper move.  A machine cannot tell where on its tape it is, so a
round does not need *clean* tapes, only *fresh* ones: advance each working
tape past everything the previous round could have written, and the region
ahead is untouched by construction.  Two clock passes per tape, no writing at
all, and the correctness argument is the same geometry — a run of `T` steps
moves a head at most `T` cells from its origin, so `2T` to the right of where
it stopped is beyond every cell it wrote.

`skipAhead` is that move: two guided passes with the clock rewound between,
leaving the clock as it found it.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-- Advance the worker by twice the clock's length, restoring the clock. -/
def skipAhead (clk w : Fin tapes) :=
  (guidedWalk clk w HeadMove.right none).andThen fun _ =>
    (rewindRun clk).andThen fun _ =>
      (guidedWalk clk w HeadMove.right none).andThen fun _ =>
        rewindRun clk

/-- One advancing round, in `cellsTape` form. -/
theorem guidedStep_skip (g w : Fin tapes) (hgw : g ≠ w)
    (T : Fin tapes → Tape) (a : TapeSymbol) (Lg Rg : List TapeSymbol)
    (hg : T g = cellsTape Lg (a :: Rg)) :
    (guidedStep g w HeadMove.right none T) g = cellsTape (a :: Lg) Rg ∧
    (guidedStep g w HeadMove.right none T) w =
      moveDir HeadMove.right (T w) := by
  constructor
  · show (if g = g then moveDir HeadMove.right (T g) else _) = _
    rw [if_pos rfl, hg, cellsTape_moveRight]
  · show (if w = g then _ else if w = w then
      moveDir HeadMove.right (T w) else _) = _
    rw [if_neg (fun h => hgw h.symm), if_pos rfl]

theorem guidedStep_skip_iterate (g w : Fin tapes) (hgw : g ≠ w) :
    ∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
      (Lg Rg : List TapeSymbol),
      T g = cellsTape Lg (marks ++ Rg) →
      (((guidedStep g w HeadMove.right none)^[marks.length]) T) g =
        cellsTape (marks.reverse ++ Lg) Rg ∧
      (((guidedStep g w HeadMove.right none)^[marks.length]) T) w =
        ((moveDir HeadMove.right)^[marks.length]) (T w) := by
  intro marks
  induction marks with
  | nil => intro T Lg Rg hg; simpa using hg
  | cons a marks ih =>
      intro T Lg Rg hg
      rw [List.length_cons, Function.iterate_succ_apply]
      obtain ⟨hg', hw'⟩ := guidedStep_skip g w hgw T a Lg (marks ++ Rg)
        (by rw [hg]; rfl)
      obtain ⟨ha, hb⟩ := ih _ (a :: Lg) Rg hg'
      refine ⟨by rw [ha]; congr 1; simp, ?_⟩
      rw [hb, hw', Function.iterate_succ_apply]

theorem guidedStep_skip_marks (g w : Fin tapes) (hgw : g ≠ w) :
    ∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
      (Lg Rg : List TapeSymbol),
      (∀ c ∈ marks, c ≠ TapeSymbol.blank) →
      T g = cellsTape Lg (marks ++ Rg) →
      ∀ r, r < marks.length →
        (((((guidedStep g w HeadMove.right none)^[r]) T) g).head ≠
          TapeSymbol.blank) := by
  intro marks
  induction marks with
  | nil => intro _ _ _ _ _ r hr; simp at hr
  | cons a marks ih =>
      intro T Lg Rg hnb hg r hr
      cases r with
      | zero =>
          simp only [Function.iterate_zero, id_eq]
          rw [hg]
          show (cellsTape Lg (a :: (marks ++ Rg))).head ≠ _
          exact hnb a (by simp)
      | succ r' =>
          rw [Function.iterate_succ_apply]
          obtain ⟨hg', -⟩ := guidedStep_skip g w hgw T a Lg (marks ++ Rg)
            (by rw [hg]; rfl)
          exact ih _ (a :: Lg) Rg (fun x hx => hnb x (by simp [hx])) hg' r'
            (by simp at hr; omega)

end SipserGacsLautemann
Source
Round primitive replacing the clock-guided erase; builds on Def_sgl_mark_back.

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