sgl_prologue_inv
DefinitionDefinition code
import Definitions.Def_sgl_input_prep
/-!
# Round zero
The prologue's four stages each leave one role in its shape; this is the
statement that those four shapes *are* the loop's invariant at round zero. It
is the join between the setup machines and the scheduler, and it is pure tape
bookkeeping — no machine runs here.
The one clause that is not simply a rewriting is the working tapes'. Their
requirement is that a walk of `2A` lands on clean tape, and a virgin scratch
tape has nothing written at all, so `skip_exhausts` discharges it from `A ≥ 1`
alone: two cells of reach are all an empty tape needs.
-/
namespace SipserGacsLautemann
open Classical
variable {n : Nat}
/-- **The prologue's output is the loop's input.** -/
theorem offsetInv_zero (L : RoundLayout n) (gd : Fin n)
(xs : Fin 3 → List TapeSymbol) (R A : Nat) (T : Fin n → Tape)
(hA : 1 ≤ A)
(hclk : T L.clk = cellsTape
(List.replicate A (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [])
(hsrc : ∀ i, T (L.src i) =
cellsTape [TapeSymbol.blank] (xs i ++ [TapeSymbol.blank]))
(hcnt : T L.cnt =
cellsTape (List.replicate (R + 1) TapeSymbol.blank) [])
(hdst : ∀ j, T (L.dst j) = cellsTape [] [])
(hgd : T gd = cellsTape []
(List.replicate R (TapeSymbol.bit true) ++ [TapeSymbol.blank])) :
OffsetInv L gd xs (fun _ => []) (fun _ => []) [] [] [] R A 0 T := by
classical
refine ⟨hclk, hsrc, ?_, ?_, ?_⟩
· rw [hcnt]
simp only [Nat.sub_zero, List.replicate_zero, List.nil_append]
rw [List.replicate_succ]
rfl
· intro j
refine skip_exhausts (T (L.dst j)) (A + A) ?_
rw [hdst j]
show ([] : List TapeSymbol).tail.length + 2 ≤ A + A
simp
omega
· rw [hgd]
simp only [Nat.sub_zero, List.replicate_zero, List.nil_append]
end SipserGacsLautemann