sgl_offset_inv
DefinitionDefinition code
import Definitions.Def_sgl_tape_extent
/-!
# The scheduler's loop invariant
`offsetRound_spec` describes one round from a tape configuration it simply
assumes. A loop needs that configuration to be *reproduced*, and the shapes do
not reproduce themselves for free — each of the five roles drifts in its own
way, and each has to be pinned so the drift lands back on the same form.
* The **clock** accumulates the delegate's steps: `A` marks become `A + Tm`,
and its left context is untouched. This is the only role that grows on
purpose — the growth is what pays for the next round's skip.
* The **inputs** are never written, only read and copied, so they sit at their
origins forever.
* The **counter** gains a mark on its left, consuming one blank from its left
context. Only a counter that starts with a blank reservoir survives; the
reservoir is sized by the round count, so `R - r` blanks remain at round `r`.
* The **working tapes** are the delicate ones. They hold the previous
delegate's leavings, and the round's precondition is that walking `2A` cells
right lands on clean tape. `sgl_tape_extent` supplies exactly this, and the
arithmetic closes because the clock grows by `Tm` while the garbage grows by
`Tm` — so the reach `2A` grows by `2·Tm` and the margin widens.
* The **guide** steps one cell right per round over a block of `R` marks, so
the head sits on mark `r` and the loop's own test reads `r + 1 < R`.
The size side-condition `roundContent … + 2 ≤ A + A` is the one thing a
prologue must arrange: a clock long enough to reach past the inputs and past
the largest offset. Once true it stays true, since `A` only grows.
-/
namespace SipserGacsLautemann
open Classical
variable {n : Nat}
/-- **The configuration between rounds.** Every role in its reproducible
shape, indexed by the round `r` and the clock's mark count `A`. -/
structure OffsetInv (L : RoundLayout n) (gd : Fin n)
(xs Ls Rs : Fin 3 → List TapeSymbol) (Lclk Lg Rg : List TapeSymbol)
(R A r : Nat) (T : Fin n → Tape) : Prop where
clk : T L.clk = cellsTape
(List.replicate A (TapeSymbol.bit true) ++ TapeSymbol.blank :: Lclk) []
src : ∀ i, T (L.src i) =
cellsTape (TapeSymbol.blank :: Ls i) (xs i ++ TapeSymbol.blank :: Rs i)
cnt : T L.cnt = cellsTape
(TapeSymbol.blank :: List.replicate (R - r) TapeSymbol.blank)
(List.replicate r (TapeSymbol.bit true) ++ [TapeSymbol.blank])
dst : ∀ j, ∃ Ld : List TapeSymbol,
((moveDir HeadMove.right)^[A + A]) (T (L.dst j)) =
cellsTape (TapeSymbol.blank :: Ld) []
gdt : T gd = cellsTape
(List.replicate r (TapeSymbol.bit true) ++ Lg)
(List.replicate (R - r) (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rg)
/-- The working tapes, as `offsetRound_spec` wants them: one list-valued
function rather than a family of existentials. -/
theorem OffsetInv.dstFun {L : RoundLayout n} {gd : Fin n}
{xs Ls Rs : Fin 3 → List TapeSymbol} {Lclk Lg Rg : List TapeSymbol}
{R A r : Nat} {T : Fin n → Tape}
(h : OffsetInv L gd xs Ls Rs Lclk Lg Rg R A r T) :
∃ Ld : Fin 4 → List TapeSymbol, ∀ j,
((moveDir HeadMove.right)^[A + A]) (T (L.dst j)) =
cellsTape (TapeSymbol.blank :: Ld j) [] := by
classical
exact ⟨fun j => (h.dst j).choose, fun j => (h.dst j).choose_spec⟩
/-! ## The clock re-enters with `A + Tm` marks -/
/-- The round hands the clock back with the delegate's steps appended to the
marks already there — which is the same shape with a larger count, provided
the clock was not empty to begin with. -/
theorem clock_reenters (A Tm : Nat) (hA : 1 ≤ A) (Lclk : List TapeSymbol) :
cellsTape (List.replicate Tm (TapeSymbol.bit true) ++
roundClockLeft A Lclk) [] =
cellsTape (List.replicate (A + Tm) (TapeSymbol.bit true) ++
TapeSymbol.blank :: Lclk) [] := by
obtain ⟨a, rfl⟩ : ∃ a, A = a + 1 := ⟨A - 1, by omega⟩
rw [roundClockLeft_succ]
congr 1
rw [← List.append_assoc, ← List.replicate_add]
congr 2
omega
/-! ## The counter re-enters with one more mark -/
/-- The bump turns the counter's shape at round `r` into its shape at round
`r + 1`, spending one blank from the reservoir. -/
theorem counter_reenters (R r : Nat) (hr : r < R) :
cellsTape (List.replicate (R - r) TapeSymbol.blank)
(List.replicate (r + 1) (TapeSymbol.bit true) ++
TapeSymbol.blank :: []) =
cellsTape (TapeSymbol.blank ::
List.replicate (R - (r + 1)) TapeSymbol.blank)
(List.replicate (r + 1) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) := by
congr 1
obtain ⟨d, hd⟩ : ∃ d, R - r = d + 1 := ⟨R - r - 1, by omega⟩
rw [hd, List.replicate_succ]
congr 2
omega
/-! ## The guide advances one mark -/
/-- Stepping the guide right moves the head from mark `r` to mark `r + 1`. -/
theorem guide_reenters (R r : Nat) (hr : r < R) (Lg Rg : List TapeSymbol) :
moveDir HeadMove.right
(cellsTape (List.replicate r (TapeSymbol.bit true) ++ Lg)
(List.replicate (R - r) (TapeSymbol.bit true) ++
TapeSymbol.blank :: Rg)) =
cellsTape (List.replicate (r + 1) (TapeSymbol.bit true) ++ Lg)
(List.replicate (R - (r + 1)) (TapeSymbol.bit true) ++
TapeSymbol.blank :: Rg) := by
obtain ⟨d, hd⟩ : ∃ d, R - r = d + 1 := ⟨R - r - 1, by omega⟩
have hd' : R - (r + 1) = d := by omega
rw [hd, hd', List.replicate_succ, List.cons_append, cellsTape_moveRight,
List.replicate_succ]
rfl
/-- **What the loop's test reads.** At round `r` the guide's head, after its
step, carries a mark exactly when another offset remains. -/
theorem guide_head (R r : Nat) (Lg Rg : List TapeSymbol) :
(cellsTape (List.replicate r (TapeSymbol.bit true) ++ Lg)
(List.replicate (R - r) (TapeSymbol.bit true) ++
TapeSymbol.blank :: Rg)).head =
if r < R then TapeSymbol.bit true else TapeSymbol.blank := by
by_cases hr : r < R
· obtain ⟨d, hd⟩ : ∃ d, R - r = d + 1 := ⟨R - r - 1, by omega⟩
rw [hd, List.replicate_succ, if_pos hr]
rfl
· have hd : R - r = 0 := by omega
rw [hd, if_neg hr]
rfl
end SipserGacsLautemann