The round's tape shape
Definitionsgl_round_stateThe round's tape shape, and the stages that establish it.
roundState L T c w is how a round presents the machine's tapes: a clock, four working tapes, and everything else carried through from the original. It is arranged so that roundState L T (cellsTape Lc []) w is the delegate's clockTapesL at zero ticks, definitionally — the delegate applies with no translation step at all, which is what keeps the round's proof from drowning in nested tape updates.
Also here: clockScan_spec, which returns the clock to virgin territory before the delegate runs, and copyBack_spec_of.
On copyBack_spec_of. The published copyBack_spec carries a hypothesis bounding the copy against the target's remaining cells. That hypothesis is unsatisfiable exactly where a round needs the copy — after a skip, the target's head sits past everything ever written, so its right context is empty and the bound forces a copy of length at most one. It is also never used: Lean's linter flags it, and the sibling markBack_spec, of identical shape, does not carry it. This module re-proves the statement without it, the proof body unchanged. Sixth instance in this campaign of a specification that is true but unusable — and the first found by the compiler rather than by a failed composition.
import Definitions.Def_sgl_skip_spec
/-!
# One round of the offset scheduler, specified
`offsetRound` chains six stages; each has a proved specification. What is
left is to thread a single tape description through all six, which is what
this module does.
Two shapes make the assembly readable.
`roundState L T c w` is the tape function a round lives on: a clock tape `c`,
four working tapes `w`, and everything else — inputs, counter — from `T`.
Every stage either rewrites the clock slot or one working slot, so the whole
round is a walk through `roundState` values, and the two `Function.update`
lemmas below are all the bookkeeping any stage needs.
`roundState L T (cellsTape Lc []) w` is *definitionally* `clockTapesL L.sel
L.clk T w Lc 0`, the shape `embedClockL_spec` consumes. The round's fifth
stage puts the clock in exactly that form, so the delegate applies with no
translation at all and the round's conclusion is a `clockTapesL` — the same
shape the next round's hypotheses read off.
-/
namespace SipserGacsLautemann
open Classical
variable {tapes : Nat}
/-! ## A copy-back onto virgin tape
`copyBack_spec` carries an unused hypothesis `cs.length ≤ Rt.length`. A tape
that a head has been advanced past everything written has *empty* right
context — `cellsTape L []` — so that hypothesis is false exactly where the
round needs the copy. The proof never uses it; this is the same proof with
the hypothesis dropped.
-/
set_option maxHeartbeats 4000000 in
/-- **Restore a tape from another**, with no constraint on the target's
written extent. The source is left exactly as it was; the target now carries
the same run, both heads on its first cell. -/
theorem copyBack_spec_of (s t : Fin tapes) (hst : s ≠ t)
(cs : List TapeSymbol) (Ls Lt Rs Rt : List TapeSymbol)
(T : Fin tapes → Tape)
(hnb : ∀ c ∈ cs, c ≠ TapeSymbol.blank)
(hs : T s = cellsTape (TapeSymbol.blank :: Ls) (cs ++ TapeSymbol.blank :: Rs))
(ht : T t = cellsTape (TapeSymbol.blank :: Lt) Rt) :
∃ cost : Nat,
HaltsExactly (copyBack s t) ((copyBack s t).startCfg T) cost true ∧
(((copyBack s t).step^[cost]) ((copyBack s t).startCfg T)).tape =
Function.update (Function.update T s
(cellsTape (TapeSymbol.blank :: Ls) (cs ++ TapeSymbol.blank :: Rs))) t
(cellsTape (TapeSymbol.blank :: Lt)
(cs ++ (Rt.drop cs.length).headD TapeSymbol.blank ::
(Rt.drop cs.length).tail)) := by
classical
obtain ⟨hC, hCt⟩ := copyRun_spec s t hst cs.length T
(copyStep_marks s t hst cs T (TapeSymbol.blank :: Ls) (TapeSymbol.blank :: Rs)
(TapeSymbol.blank :: Lt) Rt hnb (by rw [hs]) (by rw [ht]))
(by
obtain ⟨ha, -⟩ := copyStep_iterate s t hst cs T
(TapeSymbol.blank :: Ls) (TapeSymbol.blank :: Rs) (TapeSymbol.blank :: Lt) Rt
(by rw [hs]) (by rw [ht])
rw [ha]
rfl)
obtain ⟨hia, hib⟩ := copyStep_iterate s t hst cs T
(TapeSymbol.blank :: Ls) (TapeSymbol.blank :: Rs) (TapeSymbol.blank :: Lt) Rt
(by rw [hs]) (by rw [ht])
set T1 := ((copyStep s t)^[cs.length]) T with hT1
have hT1s : T1 s = cellsTape (cs.reverse ++ TapeSymbol.blank :: Ls)
(TapeSymbol.blank :: Rs) := hia
have hT1t : T1 t = cellsTape (cs.reverse ++ TapeSymbol.blank :: Lt)
(Rt.drop cs.length) := hib
obtain ⟨hRs, hRst⟩ := rewindRun_spec s cs Ls Rs TapeSymbol.blank T1
hnb (by rw [hT1s])
set T2 := Function.update T1 s
(cellsTape (TapeSymbol.blank :: Ls) (cs ++ TapeSymbol.blank :: Rs))
with hT2
have hT2t : T2 t = cellsTape (cs.reverse ++ TapeSymbol.blank :: Lt)
(Rt.drop cs.length) := by
rw [hT2, Function.update_of_ne (fun h => hst h.symm)]
exact hT1t
obtain ⟨hRt, hRtt⟩ := rewindRun_spec t cs Lt ((Rt.drop cs.length).tail)
((Rt.drop cs.length).headD TapeSymbol.blank) T2 hnb
(by rw [hT2t]; exact cellsTape_norm _ _)
refine ⟨(cs.length * 5 + 4) + 1 +
((cs.length * 4 + 3 + 1 + 1) + 1 + (cs.length * 4 + 3 + 1 + 1)), ?_, ?_⟩
· exact (chainStepC hC hCt (chainStepC hRs hRst hRt).1).1
· have hch := chainStepC hC hCt (chainStepC hRs hRst hRt).1
have hin := chainStepC hRs hRst hRt
have hfin := hch.2
rw [hin.2] at hfin
have hfin' : ((copyBack s t).step^[(cs.length * 5 + 4) + 1 +
((cs.length * 4 + 3 + 1 + 1) + 1 + (cs.length * 4 + 3 + 1 + 1))])
((copyBack s t).startCfg T) = _ := hfin
rw [hfin']
show (((rewindRun t).step^[cs.length * 4 + 3 + 1 + 1])
((rewindRun t).startCfg T2)).tape = _
rw [hRtt, hT2]
funext j
by_cases hj : j = t
· subst hj
simp only [Function.update_self]
· rw [Function.update_of_ne hj, Function.update_of_ne hj]
by_cases hj2 : j = s
· subst hj2
simp only [Function.update_self]
· rw [Function.update_of_ne hj2, Function.update_of_ne hj2, hT1]
exact copyStep_other s t hst cs.length T j hj2 hj
/-! ## The clock's closing scan
Stage five returns the clock to virgin territory. The head crosses the
accumulated marks again and stops on the blank past them — except on a clock
that has never ticked, where the head starts on a blank and the scan, which
looks *strictly beyond* the current cell, materialises one more.
-/
/-- The clock's left context once the round hands over to the delegate. -/
def roundClockLeft (A : Nat) (Lc : List TapeSymbol) : List TapeSymbol :=
match A with
| 0 => TapeSymbol.blank :: TapeSymbol.blank :: Lc
| a + 1 =>
List.replicate (a + 1) (TapeSymbol.bit true) ++ TapeSymbol.blank :: Lc
theorem roundClockLeft_zero (Lc : List TapeSymbol) :
roundClockLeft 0 Lc = TapeSymbol.blank :: TapeSymbol.blank :: Lc := rfl
theorem roundClockLeft_succ (a : Nat) (Lc : List TapeSymbol) :
roundClockLeft (a + 1) Lc =
List.replicate (a + 1) (TapeSymbol.bit true) ++ TapeSymbol.blank :: Lc :=
rfl
set_option maxHeartbeats 1000000 in
/-- **The closing scan.** From the first of `A` accumulated marks the head
returns to the blank past them. -/
theorem clockScan_spec (i : Fin tapes) (A : Nat) (Lc : List TapeSymbol)
(T : Fin tapes → Tape)
(hT : T i = cellsTape (TapeSymbol.blank :: Lc)
(List.replicate A (TapeSymbol.bit true) ++ [TapeSymbol.blank])) :
∃ cost : Nat,
HaltsExactly (scanToBlank i HeadMove.right)
((scanToBlank i HeadMove.right).startCfg T) cost false ∧
(((scanToBlank i HeadMove.right).step^[cost])
((scanToBlank i HeadMove.right).startCfg T)).tape =
Function.update T i (cellsTape (roundClockLeft A Lc) []) := by
classical
cases A with
| zero =>
have hstep : ((moveDir HeadMove.right)^[0 + 1]) (T i) =
cellsTape (TapeSymbol.blank :: TapeSymbol.blank :: Lc) [] := by
rw [hT]
have := cellsTape_advance [TapeSymbol.blank] (TapeSymbol.blank :: Lc) []
simpa using this
have hlt : ∀ k, k < 0 →
((moveDir HeadMove.right)^[k + 1] (T i)).head ≠ TapeSymbol.blank := by
intro k hk; exact absurd hk (by omega)
have heq : ((moveDir HeadMove.right)^[0 + 1] (T i)).head =
TapeSymbol.blank := by rw [hstep]; rfl
refine ⟨0 * 4 + 3, scanToBlank_spec_of i HeadMove.right T 0 hlt heq, ?_⟩
rw [scanToBlank_tape_of i HeadMove.right T 0 hlt heq, scanTapesDir, hstep]
rfl
| succ a =>
set mk := TapeSymbol.bit true with hmk
have hsplit : ∀ k, k ≤ a + 1 →
((moveDir HeadMove.right)^[k]) (T i) =
cellsTape (List.replicate k mk ++ TapeSymbol.blank :: Lc)
(List.replicate (a + 1 - k) mk ++ [TapeSymbol.blank]) := by
intro k hk
rw [hT]
have hcat : List.replicate (a + 1) mk ++ [TapeSymbol.blank] =
List.replicate k mk ++
(List.replicate (a + 1 - k) mk ++ [TapeSymbol.blank]) := by
rw [← List.append_assoc, ← List.replicate_add]
congr 2
omega
rw [hcat]
have := cellsTape_advance (List.replicate k mk) (TapeSymbol.blank :: Lc)
(List.replicate (a + 1 - k) mk ++ [TapeSymbol.blank])
rw [List.length_replicate] at this
rw [this, List.reverse_replicate]
have hlt : ∀ k, k < a →
((moveDir HeadMove.right)^[k + 1] (T i)).head ≠ TapeSymbol.blank := by
intro k hk
rw [hsplit (k + 1) (by omega)]
have hpos : a + 1 - (k + 1) = (a - 1 - k) + 1 := by omega
rw [hpos, List.replicate_succ]
show mk ≠ TapeSymbol.blank
simp [hmk]
have heq : ((moveDir HeadMove.right)^[a + 1] (T i)).head =
TapeSymbol.blank := by
rw [hsplit (a + 1) (by omega)]
rw [show a + 1 - (a + 1) = 0 by omega]
rfl
have hlt' : ∀ k, k < a →
((moveDir HeadMove.right)^[k + 1] (T i)).head ≠ TapeSymbol.blank := hlt
refine ⟨a * 4 + 3, scanToBlank_spec_of i HeadMove.right T a hlt' heq, ?_⟩
rw [scanToBlank_tape_of i HeadMove.right T a hlt' heq, scanTapesDir]
congr 1
rw [hsplit (a + 1) (by omega), show a + 1 - (a + 1) = 0 by omega]
rfl
/-! ## The state a round lives on -/
section Round
variable {n : Nat}
/-- Clock, four working tapes, and everything else from `T`. -/
noncomputable def roundState (L : RoundLayout n) (T : Fin n → Tape) (c : Tape)
(w : Fin 4 → Tape) : Fin n → Tape :=
fun i =>
if i = L.clk then c
else if h : ∃ j, L.dst j = i then w h.choose
else T i
@[simp] theorem roundState_clk (L : RoundLayout n) (T : Fin n → Tape) (c : Tape)
(w : Fin 4 → Tape) : roundState L T c w L.clk = c := by
rw [roundState, if_pos rfl]
theorem roundState_dst (L : RoundLayout n) (hL : L.Wf) (T : Fin n → Tape)
(c : Tape) (w : Fin 4 → Tape) (j : Fin 4) :
roundState L T c w (L.dst j) = w j := by
classical
rw [roundState, if_neg (hL.clk_dst j)]
have hex : ∃ j', L.dst j' = L.dst j := ⟨j, rfl⟩
rw [dif_pos hex]
congr 1
exact hL.dst_inj hex.choose_spec
theorem roundState_other (L : RoundLayout n) (T : Fin n → Tape) (c : Tape)
(w : Fin 4 → Tape) (i : Fin n) (hi : i ≠ L.clk) (hni : ∀ j, L.dst j ≠ i) :
roundState L T c w i = T i := by
classical
rw [roundState, if_neg hi, dif_neg (fun h => (hni h.choose) h.choose_spec)]
theorem roundState_update_clk (L : RoundLayout n) (T : Fin n → Tape)
(c c' : Tape) (w : Fin 4 → Tape) :
Function.update (roundState L T c w) L.clk c' = roundState L T c' w := by
classical
funext i
by_cases hi : i = L.clk
· subst hi; rw [Function.update_self, roundState_clk]
· rw [Function.update_of_ne hi, roundState, roundState, if_neg hi, if_neg hi]
theorem roundState_update_dst (L : RoundLayout n) (hL : L.Wf) (T : Fin n → Tape)
(c : Tape) (w : Fin 4 → Tape) (j : Fin 4) (v : Tape) :
Function.update (roundState L T c w) (L.dst j) v =
roundState L T c (Function.update w j v) := by
classical
funext i
by_cases hi : i = L.dst j
· subst hi
rw [Function.update_self, roundState_dst L hL, Function.update_self]
· rw [Function.update_of_ne hi]
by_cases hclk : i = L.clk
· subst hclk; rw [roundState_clk, roundState_clk]
· by_cases hex : ∃ j', L.dst j' = i
· obtain ⟨j', hj'⟩ := hex
subst hj'
rw [roundState_dst L hL, roundState_dst L hL,
Function.update_of_ne (fun h => hi (by rw [h]))]
· rw [roundState_other L T c w i hclk (fun j' hj' => hex ⟨j', hj'⟩),
roundState_other L T c (Function.update w j v) i hclk
(fun j' hj' => hex ⟨j', hj'⟩)]
/-- The round's first stage turns `T` into a `roundState`. -/
theorem roundState_start (L : RoundLayout n) (hL : L.Wf) (T : Fin n → Tape)
(c : Tape) :
Function.update T L.clk c = roundState L T c (fun j => T (L.dst j)) := by
classical
funext i
by_cases hi : i = L.clk
· subst hi; rw [Function.update_self, roundState_clk]
· rw [Function.update_of_ne hi]
by_cases hex : ∃ j, L.dst j = i
· obtain ⟨j, hj⟩ := hex
subst hj
rw [roundState_dst L hL]
· rw [roundState_other L T c _ i hi (fun j hj => hex ⟨j, hj⟩)]
/-- A round state whose clock sits on virgin tape *is* the delegate's shape. -/
theorem roundState_clockTapesL (L : RoundLayout n) (T : Fin n → Tape)
(w : Fin 4 → Tape) (Lc : List TapeSymbol) :
roundState L T (cellsTape Lc []) w = clockTapesL L.sel L.clk T w Lc 0 := rfl
/-- Four updates at the four working slots rewrite every one of them. -/
theorem update_four (w V : Fin 4 → Tape) :
Function.update (Function.update (Function.update
(Function.update w 0 (V 0)) 1 (V 1)) 2 (V 2)) 3 (V 3) = V := by
funext j
fin_cases j <;> rfl
/-! ## Stage two: advance every working tape -/
end Round
end SipserGacsLautemann