Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_skip_margin

Definition

by Henry Yuen · Jul 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

Definition code
import Definitions.Def_sgl_tape_locality

/-!
# How much blank the skip leaves behind

`skip_exhausts` says a long enough rightward walk lands on clean tape.  It says
nothing about what is behind the head, and behind the head is where the
previous round's leavings are.  For a delegate to be unable to reach them, the
walk has to overshoot by more than the delegate's own time bound, and the
statement has to record that it did.

The count is exact: a walk of `m` over a written region of length `q` puts
`m - q - 1` blanks between the head and the leavings, because every cell past
the region is one the head has never visited.  Asking for `q + p + 2 ≤ m` is
asking for `p` of them.
-/

namespace SipserGacsLautemann

/-- **The skip, with its margin.**  A walk that overshoots the written region
by `p + 2` leaves at least `p` blanks behind the head before anything else. -/
theorem skipRight_exhausts_blanks :
    ∀ (R L : List TapeSymbol) (h : TapeSymbol) (m p : Nat),
    R.length + p + 2 ≤ m →
    ∃ L' : List TapeSymbol,
      ((moveDir HeadMove.right)^[m]) (⟨L, h, R⟩ : Tape) =
        cellsTape (TapeSymbol.blank ::
          (List.replicate p TapeSymbol.blank ++ L')) [] := by
  intro R
  induction R with
  | nil =>
      intro L h m p hm
      obtain ⟨m', rfl⟩ : ∃ m', m = m' + 2 := ⟨m - 2, by simp at hm; omega⟩
      refine ⟨List.replicate (m' - p) TapeSymbol.blank ++ h :: L, ?_⟩
      rw [moveRight_past_nil L h m']
      congr 2
      rw [← List.append_assoc, ← List.replicate_add]
      congr 2
      simp at hm
      omega
  | cons s R ih =>
      intro L h m p hm
      obtain ⟨m', rfl⟩ : ∃ m', m = m' + 1 := ⟨m - 1, by simp at hm; omega⟩
      rw [Function.iterate_succ_apply]
      have hstep : moveDir HeadMove.right (⟨L, h, s :: R⟩ : Tape) =
          ⟨h :: L, s, R⟩ := rfl
      rw [hstep]
      exact ih (h :: L) s m' p (by simp at hm; omega)

/-- The same, for a tape given abstractly. -/
theorem skip_exhausts_blanks (tp : Tape) (m p : Nat)
    (hm : tp.right.length + p + 2 ≤ m) :
    ∃ L' : List TapeSymbol,
      ((moveDir HeadMove.right)^[m]) tp =
        cellsTape (TapeSymbol.blank ::
          (List.replicate p TapeSymbol.blank ++ L')) [] := by
  cases tp with
  | mk L h R => exact skipRight_exhausts_blanks R L h m p hm

/-- **The re-entry condition, with a margin.** -/
theorem delegate_leaves_skippable_blanks {tapes states : Nat}
    (M : Machine tapes states) (cfg : Configuration tapes states)
    (j : Fin tapes) (Tm q m p : Nat)
    (hq : (cfg.tape j).right.length ≤ q)
    (hm : q + Tm + p + 2 ≤ m) :
    ∃ L' : List TapeSymbol,
      ((moveDir HeadMove.right)^[m]) (((M.step^[Tm]) cfg).tape j) =
        cellsTape (TapeSymbol.blank ::
          (List.replicate p TapeSymbol.blank ++ L')) [] := by
  refine skip_exhausts_blanks _ m p ?_
  have := right_length_run M cfg j Tm
  omega

/-! ## What a margin buys -/

/-- A tape whose left context begins with `t` blanks agrees, out to radius `t`,
with the same tape read from an empty left context. -/
theorem agree_of_blank_margin (p : Nat) (L' R : List TapeSymbol)
    (t : Nat) (ht : t ≤ p + 1) :
    TapeAgree t
      (cellsTape (TapeSymbol.blank ::
        (List.replicate p TapeSymbol.blank ++ L')) R)
      (cellsTape [] R) := by
  refine ⟨rfl, ?_, fun i _ => rfl⟩
  intro i hi
  show (TapeSymbol.blank ::
    (List.replicate p TapeSymbol.blank ++ L')).getD i TapeSymbol.blank =
    ([] : List TapeSymbol).getD i TapeSymbol.blank
  rw [List.getD_nil]
  cases i with
  | zero => rfl
  | succ i =>
      show (List.replicate p TapeSymbol.blank ++ L').getD i TapeSymbol.blank
        = TapeSymbol.blank
      rw [List.getD_eq_getElem?_getD, List.getElem?_append_left (by rw [List.length_replicate]; omega)]
      simp

end SipserGacsLautemann

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