sgl_tape_extent
DefinitionDefinition code
import Definitions.Def_sgl_counter_stable
/-!
# How far a run can spread, and how far a skip must reach
The offset scheduler reuses the same four working tapes for every round, so
each round starts on top of the previous round's leavings. `advanceAll` walks
each working tape `2A` cells to the right, where `A` is the clock's mark count,
and the round then assumes it has landed on clean tape. Nothing so far
*justifies* that assumption.
The justification is a length count. A tape is a zipper, and the only thing a
step can do to the right half is push one cell onto it (a leftward move) or pop
one off (a rightward move). So the right half grows by at most one cell per
step, and a machine run for `t` steps leaves a right half no longer than it
started plus `t`. A rightward walk that exceeds that length by two runs off the
end of the written region and stands on blank tape with nothing beyond it —
which is exactly the shape the next round wants.
The two cells of slack are not slack: one right-move is needed to consume the
final written cell, and one more to put a *blank* into the left context, since
the round's precondition names the cell immediately left of the head.
This is what makes the loop's invariant self-sustaining. Each round the clock
gains `Tm` marks, so the reach `2A` grows by `2·Tm`, while the garbage grows by
only `Tm`. The margin widens every round, so one sufficiently long clock at the
start carries the invariant forever.
-/
namespace SipserGacsLautemann
variable {tapes states : Nat}
/-! ## One step spreads by at most one cell -/
/-- Writing then moving lengthens the right half by at most one. -/
theorem right_length_move_write (tp : Tape) (c : TapeSymbol) (d : HeadMove) :
(Tape.move (Tape.write tp c) d).right.length ≤ tp.right.length + 1 := by
cases d with
| stay => simp [Tape.move, Tape.write]
| left =>
cases tp with
| mk L h R =>
cases L with
| nil => simp [Tape.move, Tape.write]
| cons s L => simp [Tape.move, Tape.write]
| right =>
cases tp with
| mk L h R =>
cases R with
| nil => simp [Tape.move, Tape.write]
| cons s R => simp [Tape.move, Tape.write]; omega
/-- A machine step lengthens each right half by at most one. -/
theorem right_length_step (M : Machine tapes states)
(cfg : Configuration tapes states) (j : Fin tapes) :
((M.step cfg).tape j).right.length ≤ (cfg.tape j).right.length + 1 := by
rw [Machine.step]
cases hres : M.result cfg.state with
| some v => simp
| none => exact right_length_move_write _ _ _
/-- **The spread bound.** After `t` steps every right half has grown by at
most `t` cells. -/
theorem right_length_run (M : Machine tapes states)
(cfg : Configuration tapes states) (j : Fin tapes) (t : Nat) :
(((M.step^[t]) cfg).tape j).right.length ≤ (cfg.tape j).right.length + t := by
induction t generalizing cfg with
| zero => simp
| succ t ih =>
rw [Function.iterate_succ_apply]
have h1 := ih (M.step cfg)
have h2 := right_length_step M cfg j
omega
/-! ## A long enough walk lands on clean tape -/
/-- A walk that has already exhausted the right half keeps standing on blank
tape, accumulating blanks behind it. -/
theorem moveRight_past_nil (L : List TapeSymbol) (h : TapeSymbol) (m : Nat) :
((moveDir HeadMove.right)^[m + 2]) (⟨L, h, []⟩ : Tape) =
cellsTape (TapeSymbol.blank ::
(List.replicate m TapeSymbol.blank ++ h :: L)) [] := by
induction m with
| zero => rfl
| succ m ih =>
rw [show m + 1 + 2 = (m + 2) + 1 from rfl, Function.iterate_succ_apply', ih]
rw [cellsTape_moveRight_nil]
simp [cellsTape, List.replicate_succ]
/-- **The skip lands clean.** A rightward walk two cells longer than the
written region ends on blank tape, with a blank immediately to its left and
nothing at all to its right. -/
theorem skipRight_exhausts : ∀ (R L : List TapeSymbol) (h : TapeSymbol) (m : Nat),
R.length + 2 ≤ m →
∃ L' : List TapeSymbol,
((moveDir HeadMove.right)^[m]) (⟨L, h, R⟩ : Tape) =
cellsTape (TapeSymbol.blank :: L') [] := by
intro R
induction R with
| nil =>
intro L h m hm
obtain ⟨m', rfl⟩ : ∃ m', m = m' + 2 := ⟨m - 2, by simp at hm; omega⟩
exact ⟨List.replicate m' TapeSymbol.blank ++ h :: L,
moveRight_past_nil L h m'⟩
| cons s R ih =>
intro L h m 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' (by simp at hm; omega)
/-- The same, for a tape given abstractly. -/
theorem skip_exhausts (tp : Tape) (m : Nat) (hm : tp.right.length + 2 ≤ m) :
∃ L' : List TapeSymbol,
((moveDir HeadMove.right)^[m]) tp = cellsTape (TapeSymbol.blank :: L') [] := by
cases tp with
| mk L h R => exact skipRight_exhausts R L h m hm
/-! ## What the next round inherits -/
/-- **The re-entry condition.** If a delegate ran `Tm` steps from tapes whose
right halves were no longer than `q`, then a walk of `m ≥ q + Tm + 2` cells
lands each of its tapes on clean tape.
This is the hypothesis `offsetRound_spec` calls `hdst`, established for the
round *after* a delegated run rather than assumed. -/
theorem delegate_leaves_skippable (M : Machine tapes states)
(cfg : Configuration tapes states) (j : Fin tapes) (Tm q m : Nat)
(hq : (cfg.tape j).right.length ≤ q)
(hm : q + Tm + 2 ≤ m) :
∃ L' : List TapeSymbol,
((moveDir HeadMove.right)^[m]) (((M.step^[Tm]) cfg).tape j) =
cellsTape (TapeSymbol.blank :: L') [] := by
refine skip_exhausts _ m ?_
have := right_length_run M cfg j Tm
omega
end SipserGacsLautemann