sgl_tape_locality
DefinitionDefinition 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