Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The skip, specified

Definition
sgl_skip_spec

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The skip, specified. Two guided passes over the clock advance the worker by twice the clock's length and leave the clock exactly as it was — the form a round consumes four times, once per working tape.

The worker's new position is stated as (moveDir right)[2m](\mathrm{moveDir\ right})^{[2m]}(moveDir right)[2m] applied to its tape, which is the formulation that survives the worker running off the end of its written region; every other tape is untouched. The clock's restoration is what makes the four uses independent: each skip can assume the same clock shape as the last left it.

This completes the primitive published earlier with only its per-round lemmas. Every stage of the round now has a top-level statement: rewind, skip, restore, mark, and delegate.

Definition code
import Definitions.Def_sgl_offset_round

/-!
# The skip, specified

`skipAhead` was defined with its per-round lemmas; this is its top-level
statement.  Two guided passes over the clock advance the worker by twice the
clock's length and leave the clock exactly as it was — the form a round
consumes four times.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

set_option maxHeartbeats 4000000 in
/-- **Advance the worker by twice the clock's marks, clock restored.** -/
theorem skipAhead_spec (clk w : Fin tapes) (hcw : clk ≠ w)
    (marks Lc Rc : List TapeSymbol) (T : Fin tapes → Tape)
    (hnb : ∀ x ∈ marks, x ≠ TapeSymbol.blank)
    (hc : T clk = cellsTape (TapeSymbol.blank :: Lc)
      (marks ++ TapeSymbol.blank :: Rc)) :
    ∃ cost : Nat,
      HaltsExactly (skipAhead clk w) ((skipAhead clk w).startCfg T) cost true ∧
      (((skipAhead clk w).step^[cost])
        ((skipAhead clk w).startCfg T)).tape =
        Function.update T w
          (((moveDir HeadMove.right)^[marks.length + marks.length]) (T w)) := by
  classical
  set G := guidedStep clk w HeadMove.right none with hG
  -- first pass
  obtain ⟨h1a, h1b⟩ := guidedStep_skip_iterate clk w hcw marks T
    (TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hc])
  obtain ⟨hW1, hW1t⟩ := guidedWalk_spec clk w hcw HeadMove.right none
    marks.length T
    (guidedStep_skip_marks clk w hcw marks T (TapeSymbol.blank :: Lc)
      (TapeSymbol.blank :: Rc) hnb (by rw [hc]))
    (by rw [h1a]; rfl)
  set T1 := (G^[marks.length]) T with hT1
  have hT1c : T1 clk = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
      (TapeSymbol.blank :: Rc) := h1a
  have hT1w : T1 w = ((moveDir HeadMove.right)^[marks.length]) (T w) := h1b
  -- first rewind
  obtain ⟨hR1, hR1t⟩ := rewindRun_spec clk marks Lc Rc TapeSymbol.blank T1
    hnb (by rw [hT1c])
  set T2 := Function.update T1 clk
    (cellsTape (TapeSymbol.blank :: Lc) (marks ++ TapeSymbol.blank :: Rc))
    with hT2
  have hT2c : T2 clk = cellsTape (TapeSymbol.blank :: Lc)
      (marks ++ TapeSymbol.blank :: Rc) := by rw [hT2]; simp
  have hT2w : T2 w = ((moveDir HeadMove.right)^[marks.length]) (T w) := by
    rw [hT2, Function.update_of_ne (fun h => hcw h.symm)]
    exact hT1w
  -- second pass
  obtain ⟨h2a, h2b⟩ := guidedStep_skip_iterate clk w hcw marks T2
    (TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hT2c])
  obtain ⟨hW2, hW2t⟩ := guidedWalk_spec clk w hcw HeadMove.right none
    marks.length T2
    (guidedStep_skip_marks clk w hcw marks T2 (TapeSymbol.blank :: Lc)
      (TapeSymbol.blank :: Rc) hnb (by rw [hT2c]))
    (by rw [h2a]; rfl)
  set T3 := (G^[marks.length]) T2 with hT3
  have hT3c : T3 clk = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
      (TapeSymbol.blank :: Rc) := h2a
  -- second rewind
  obtain ⟨hR2, hR2t⟩ := rewindRun_spec clk marks Lc Rc TapeSymbol.blank T3
    hnb (by rw [hT3c])
  refine ⟨_, (chainStepC hW1 hW1t (chainStepC hR1 hR1t
    (chainStepC hW2 hW2t hR2).1).1).1, ?_⟩
  have hin2 := chainStepC hW2 hW2t hR2
  have hin1 := chainStepC hR1 hR1t hin2.1
  have hch := chainStepC hW1 hW1t hin1.1
  have hfin := hch.2
  rw [hin1.2, hin2.2] at hfin
  have hfin' : ((skipAhead clk w).step^[_])
      ((skipAhead clk w).startCfg T) = _ := hfin
  rw [hfin']
  show (((rewindRun clk).step^[_]) ((rewindRun clk).startCfg T3)).tape = _
  rw [hR2t]
  funext j
  by_cases hj : j = clk
  · subst hj
    rw [Function.update_self, Function.update_of_ne hcw, hc]
  · rw [Function.update_of_ne hj]
    by_cases hj2 : j = w
    · subst hj2
      rw [Function.update_self, h2b, hT2w, ← Function.iterate_add_apply]
    · rw [Function.update_of_ne hj2, hT3,
        guidedStep_other clk w HeadMove.right none marks.length T2 j hj hj2,
        hT2, Function.update_of_ne hj, hT1,
        guidedStep_other clk w HeadMove.right none marks.length T j hj hj2]

end SipserGacsLautemann
Source
Top-level statement for skipAhead; builds on Def_sgl_offset_round.

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