Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_tape_locality

Definition

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

Definition code
import Definitions.Def_sgl_scheduler

/-!
# A run only sees what it can reach

A machine given `t` steps can move each head at most `t` cells, so its
behaviour depends only on the cells within distance `t` of where it started.
Two tape configurations that agree on that window are indistinguishable for
`t` steps: same states throughout, same verdict.

This is what lets a delegate be run on tapes that are not the ones its
correctness was stated for.  The scheduler hands its delegate tapes whose
distant left context holds the previous round's leavings, and whose right
context carries an extra terminating blank; neither is reachable inside the
delegate's own time bound, provided the blank margin between the head and the
leavings is at least that bound.

Cells are addressed by distance rather than by list position, because the two
representations of the same tape disagree about list positions — a tape with an
empty left half and one with a blank there denote the same cells.  Reading
through `getD … blank` is what makes the two agree.
-/

namespace SipserGacsLautemann

variable {k states : Nat}

/-- The `i`-th cell left of the head; blank past the written region. -/
def leftAt (tp : Tape) (i : Nat) : TapeSymbol := tp.left.getD i TapeSymbol.blank

/-- The `i`-th cell right of the head. -/
def rightAt (tp : Tape) (i : Nat) : TapeSymbol := tp.right.getD i TapeSymbol.blank

/-- Two tapes agree on the window of radius `t`. -/
structure TapeAgree (t : Nat) (a b : Tape) : Prop where
  head : a.head = b.head
  left : ∀ i, i < t → leftAt a i = leftAt b i
  right : ∀ i, i < t → rightAt a i = rightAt b i

/-! ## Moves, uniformly -/

theorem moveLeft_eq (tp : Tape) :
    Tape.move tp HeadMove.left =
      ⟨tp.left.tail, tp.left.headD TapeSymbol.blank, tp.head :: tp.right⟩ := by
  cases tp with
  | mk L h R => cases L with
    | nil => rfl
    | cons s L => rfl

theorem moveRight_eq (tp : Tape) :
    Tape.move tp HeadMove.right =
      ⟨tp.head :: tp.left, tp.right.headD TapeSymbol.blank, tp.right.tail⟩ := by
  cases tp with
  | mk L h R => cases R with
    | nil => rfl
    | cons s R => rfl

theorem headD_eq_getD (l : List TapeSymbol) :
    l.headD TapeSymbol.blank = l.getD 0 TapeSymbol.blank := by
  cases l <;> rfl

theorem getD_tail (l : List TapeSymbol) (i : Nat) :
    l.tail.getD i TapeSymbol.blank = l.getD (i + 1) TapeSymbol.blank := by
  cases l <;> rfl

/-! ## Reading the moved tape -/

theorem head_moveLeft (tp : Tape) :
    (Tape.move tp HeadMove.left).head = leftAt tp 0 := by
  rw [moveLeft_eq]
  exact headD_eq_getD tp.left

theorem leftAt_moveLeft (tp : Tape) (i : Nat) :
    leftAt (Tape.move tp HeadMove.left) i = leftAt tp (i + 1) := by
  rw [moveLeft_eq]
  exact getD_tail tp.left i

theorem rightAt_moveLeft_zero (tp : Tape) :
    rightAt (Tape.move tp HeadMove.left) 0 = tp.head := by
  rw [moveLeft_eq]; rfl

theorem rightAt_moveLeft_succ (tp : Tape) (i : Nat) :
    rightAt (Tape.move tp HeadMove.left) (i + 1) = rightAt tp i := by
  rw [moveLeft_eq]; rfl

theorem head_moveRight (tp : Tape) :
    (Tape.move tp HeadMove.right).head = rightAt tp 0 := by
  rw [moveRight_eq]
  exact headD_eq_getD tp.right

theorem rightAt_moveRight (tp : Tape) (i : Nat) :
    rightAt (Tape.move tp HeadMove.right) i = rightAt tp (i + 1) := by
  rw [moveRight_eq]
  exact getD_tail tp.right i

theorem leftAt_moveRight_zero (tp : Tape) :
    leftAt (Tape.move tp HeadMove.right) 0 = tp.head := by
  rw [moveRight_eq]; rfl

theorem leftAt_moveRight_succ (tp : Tape) (i : Nat) :
    leftAt (Tape.move tp HeadMove.right) (i + 1) = leftAt tp i := by
  rw [moveRight_eq]; rfl

@[simp] theorem leftAt_write (tp : Tape) (c : TapeSymbol) (i : Nat) :
    leftAt (Tape.write tp c) i = leftAt tp i := rfl

@[simp] theorem rightAt_write (tp : Tape) (c : TapeSymbol) (i : Nat) :
    rightAt (Tape.write tp c) i = rightAt tp i := rfl

@[simp] theorem head_write (tp : Tape) (c : TapeSymbol) :
    (Tape.write tp c).head = c := rfl

/-! ## One step shrinks the window by one -/

set_option maxHeartbeats 1000000 in
/-- **Agreement is preserved, one cell narrower.** -/
theorem agree_step (t : Nat) (a b : Tape) (h : TapeAgree (t + 1) a b)
    (c : TapeSymbol) (d : HeadMove) :
    TapeAgree t (Tape.move (Tape.write a c) d)
      (Tape.move (Tape.write b c) d) := by
  cases d with
  | stay =>
      exact ⟨rfl, fun i hi => h.left i (by omega),
        fun i hi => h.right i (by omega)⟩
  | left =>
      refine ⟨?_, ?_, ?_⟩
      · rw [head_moveLeft, head_moveLeft, leftAt_write, leftAt_write]
        exact h.left 0 (by omega)
      · intro i hi
        rw [leftAt_moveLeft, leftAt_moveLeft, leftAt_write, leftAt_write]
        exact h.left (i + 1) (by omega)
      · intro i hi
        cases i with
        | zero => rw [rightAt_moveLeft_zero, rightAt_moveLeft_zero]
                  rfl
        | succ i =>
            rw [rightAt_moveLeft_succ, rightAt_moveLeft_succ, rightAt_write,
              rightAt_write]
            exact h.right i (by omega)
  | right =>
      refine ⟨?_, ?_, ?_⟩
      · rw [head_moveRight, head_moveRight, rightAt_write, rightAt_write]
        exact h.right 0 (by omega)
      · intro i hi
        cases i with
        | zero => rw [leftAt_moveRight_zero, leftAt_moveRight_zero]
                  rfl
        | succ i =>
            rw [leftAt_moveRight_succ, leftAt_moveRight_succ, leftAt_write,
              leftAt_write]
            exact h.left i (by omega)
      · intro i hi
        rw [rightAt_moveRight, rightAt_moveRight, rightAt_write, rightAt_write]
        exact h.right (i + 1) (by omega)

/-! ## A bounded run cannot tell the difference -/

set_option maxHeartbeats 1000000 in
/-- **Locality.**  While the window lasts, two agreeing configurations run
through the same states and keep agreeing. -/
theorem run_agree (M : Machine k states) :
    ∀ (r : Nat) (t : Nat) (s : Fin states) (T₁ T₂ : Fin k → Tape), r ≤ t →
      (∀ j, TapeAgree t (T₁ j) (T₂ j)) →
      ((M.step^[r]) ⟨s, T₁⟩).state = ((M.step^[r]) ⟨s, T₂⟩).state ∧
      (∀ j, TapeAgree (t - r) (((M.step^[r]) ⟨s, T₁⟩).tape j)
        (((M.step^[r]) ⟨s, T₂⟩).tape j)) := by
  intro r
  induction r with
  | zero =>
      intro t s T₁ T₂ _ h
      exact ⟨rfl, by simpa using h⟩
  | succ r ih =>
      intro t s T₁ T₂ hrt h
      obtain ⟨t', rfl⟩ : ∃ t', t = t' + 1 := ⟨t - 1, by omega⟩
      have hsym : (fun i => (T₁ i).head) = (fun i => (T₂ i).head) := by
        funext i
        exact (h i).head
      have hstep : ∀ (P : Fin k → Tape),
          M.step ⟨s, P⟩ =
            (match M.result s with
              | some _ => ⟨s, P⟩
              | none =>
                  ⟨(M.transition s (fun i => (P i).head)).1,
                    fun i => Tape.move
                      (Tape.write (P i)
                        ((M.transition s (fun i => (P i).head)).2 i).1)
                      ((M.transition s (fun i => (P i).head)).2 i).2⟩) :=
        fun P => rfl
      rw [Function.iterate_succ_apply, Function.iterate_succ_apply,
        hstep T₁, hstep T₂]
      cases hres : M.result s with
      | some v =>
          simp only [hres]
          exact ih (t' + 1) s T₁ T₂ (by omega)
            (fun j => ⟨(h j).head, fun i hi => (h j).left i hi,
              fun i hi => (h j).right i hi⟩) |>.imp id
            (fun hh j => ⟨(hh j).head, fun i hi => (hh j).left i (by omega),
              fun i hi => (hh j).right i (by omega)⟩)
      | none =>
          simp only [hres, hsym]
          have hag : ∀ j, TapeAgree t'
              (Tape.move (Tape.write (T₁ j)
                ((M.transition s (fun i => (T₂ i).head)).2 j).1)
                ((M.transition s (fun i => (T₂ i).head)).2 j).2)
              (Tape.move (Tape.write (T₂ j)
                ((M.transition s (fun i => (T₂ i).head)).2 j).1)
                ((M.transition s (fun i => (T₂ i).head)).2 j).2) :=
            fun j => agree_step t' (T₁ j) (T₂ j) (h j) _ _
          have := ih t' (M.transition s (fun i => (T₂ i).head)).1 _ _
            (by omega) hag
          exact ⟨this.1, by simpa using this.2⟩

/-- **The verdict is the same.**  A halting run inside the window transfers. -/
theorem halts_agree (M : Machine k states) (T₁ T₂ : Fin k → Tape)
    (t Tm : Nat) (v : Bool) (hTm : Tm ≤ t)
    (h : ∀ j, TapeAgree t (T₁ j) (T₂ j))
    (hlive : ∀ r, r < Tm →
      M.result ((M.step^[r]) ⟨M.start, T₁⟩).state = none)
    (hhalt : M.result ((M.step^[Tm]) ⟨M.start, T₁⟩).state = some v) :
    (∀ r, r < Tm →
      M.result ((M.step^[r]) ⟨M.start, T₂⟩).state = none) ∧
    M.result ((M.step^[Tm]) ⟨M.start, T₂⟩).state = some v := by
  refine ⟨fun r hr => ?_, ?_⟩
  · rw [← (run_agree M r t M.start T₁ T₂ (by omega) h).1]
    exact hlive r hr
  · rw [← (run_agree M Tm t M.start T₁ T₂ hTm h).1]
    exact hhalt

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