One round of the scheduler, proved
Definitionsgl_round_specOne round of the bounded-existential scheduler, proved. From tapes holding the three inputs, a persistent unary counter, and a clock carrying the accumulated marks of previous rounds, the round runs the delegate on exactly and halts with the delegate's own verdict.
The conclusion is stated over the original tape function, so the inputs and counter come back exactly as they were and the next round reads its hypotheses straight off this shape — no congruence step between iterations.
advanceAll_spec and restoreInputs_spec state the two composite stages with the resulting tape function as an argument plus pinning hypotheses, rather than as a nest of Function.updates. That is what keeps the caller free of update bookkeeping, and it is the same interface discipline that made the merge stack's per-step theorem close.
Two facts worth recording. A layout must require that no input tape is the clock — the round rewinds the clock before copying the inputs, so if they coincided an input would no longer be at its origin when copied; this is not derivable from the other distinctness conditions. And there is an edge at zero ticks: on a never-ticked clock the parking scan looks strictly beyond the head and materialises one extra blank, so the clock's left context shifts by one in the first round only. The loop invariant survives either way, and both cases are provided as lemmas.
import Definitions.Def_sgl_round_state
/-!
# The round, specified
The two composite stages and the round theorem itself. Split from
`sgl_round_state` for verification size.
-/
namespace SipserGacsLautemann
section Round
variable {n : Nat}
set_option maxHeartbeats 4000000 in
/-- **The four skips.** Each working tape is advanced by twice the clock's
marks; the clock is left exactly as it was found. -/
theorem advanceAll_spec (L : RoundLayout n) (hL : L.Wf) (A : Nat)
(Lc Rc : List TapeSymbol) (T : Fin n → Tape) (c : Tape) (w V : Fin 4 → Tape)
(hc : c = cellsTape (TapeSymbol.blank :: Lc)
(List.replicate A (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rc))
(hV : ∀ j, ((moveDir HeadMove.right)^[A + A]) (w j) = V j) :
∃ cost : Nat,
HaltsExactly (advanceAll L)
((advanceAll L).startCfg (roundState L T c w)) cost true ∧
(((advanceAll L).step^[cost])
((advanceAll L).startCfg (roundState L T c w))).tape =
roundState L T c V := by
classical
have hnb : ∀ x ∈ List.replicate A (TapeSymbol.bit true),
x ≠ TapeSymbol.blank := by
intro x hx
rw [List.eq_of_mem_replicate hx]
simp
-- one skip, in `roundState` form
have step : ∀ (u : Fin 4 → Tape) (j : Fin 4),
∃ cost : Nat,
HaltsExactly (skipAhead L.clk (L.dst j))
((skipAhead L.clk (L.dst j)).startCfg (roundState L T c u)) cost true ∧
(((skipAhead L.clk (L.dst j)).step^[cost])
((skipAhead L.clk (L.dst j)).startCfg (roundState L T c u))).tape =
roundState L T c
(Function.update u j (((moveDir HeadMove.right)^[A + A]) (u j))) := by
intro u j
obtain ⟨cost, hh, htp⟩ :=
skipAhead_spec L.clk (L.dst j) (hL.skip_ne j)
(List.replicate A (TapeSymbol.bit true)) Lc Rc (roundState L T c u) hnb
(by rw [roundState_clk, hc])
refine ⟨cost, hh, ?_⟩
rw [htp, roundState_dst L hL, List.length_replicate,
roundState_update_dst L hL]
obtain ⟨c0, h0, t0⟩ := step w 0
rw [hV 0] at t0
obtain ⟨c1, h1, t1⟩ := step (Function.update w 0 (V 0)) 1
rw [show (Function.update w 0 (V 0)) 1 = w 1 from
Function.update_of_ne (by decide) _ _, hV 1] at t1
obtain ⟨c2, h2, t2⟩ :=
step (Function.update (Function.update w 0 (V 0)) 1 (V 1)) 2
rw [show (Function.update (Function.update w 0 (V 0)) 1 (V 1)) 2 = w 2 by
rw [Function.update_of_ne (by decide), Function.update_of_ne (by decide)],
hV 2] at t2
obtain ⟨c3, h3, t3⟩ :=
step (Function.update (Function.update
(Function.update w 0 (V 0)) 1 (V 1)) 2 (V 2)) 3
rw [show (Function.update (Function.update
(Function.update w 0 (V 0)) 1 (V 1)) 2 (V 2)) 3 = w 3 by
rw [Function.update_of_ne (by decide), Function.update_of_ne (by decide),
Function.update_of_ne (by decide)],
hV 3, update_four w V] at t3
have cc2 := chainStepC h2 t2 h3
have cc1 := chainStepC h1 t1 cc2.1
have cc0 := chainStepC h0 t0 cc1.1
refine ⟨_, cc0.1, ?_⟩
have hfin := cc0.2
rw [cc1.2, cc2.2] at hfin
have hfin' : ((advanceAll L).step^[c0 + 1 + (c1 + 1 + (c2 + 1 + c3))])
((advanceAll L).startCfg (roundState L T c w)) = _ := hfin
rw [hfin']
show (((skipAhead L.clk (L.dst 3)).step^[c3])
((skipAhead L.clk (L.dst 3)).startCfg (roundState L T c
(Function.update (Function.update
(Function.update w 0 (V 0)) 1 (V 1)) 2 (V 2))))).tape = _
rw [t3]
/-! ## Stage three: put the inputs back -/
set_option maxHeartbeats 4000000 in
/-- **The three copies.** Each input is restored onto its working tape, the
originals untouched and every head on the run's first cell. -/
theorem restoreInputs_spec (L : RoundLayout n) (hL : L.Wf)
(hsc : ∀ i, L.src i ≠ L.clk) (T : Fin n → Tape) (c : Tape)
(w V : Fin 4 → Tape) (xs Ls Rs : Fin 3 → List TapeSymbol)
(Ld : Fin 4 → List TapeSymbol)
(hnb : ∀ i, ∀ x ∈ xs i, x ≠ TapeSymbol.blank)
(hsrc : ∀ i, T (L.src i) =
cellsTape (TapeSymbol.blank :: Ls i) (xs i ++ TapeSymbol.blank :: Rs i))
(hw : ∀ j, w j = cellsTape (TapeSymbol.blank :: Ld j) [])
(hV0 : V 0 =
cellsTape (TapeSymbol.blank :: Ld 0) (xs 0 ++ [TapeSymbol.blank]))
(hV1 : V 1 =
cellsTape (TapeSymbol.blank :: Ld 1) (xs 1 ++ [TapeSymbol.blank]))
(hV2 : V 2 =
cellsTape (TapeSymbol.blank :: Ld 2) (xs 2 ++ [TapeSymbol.blank]))
(hV3 : V 3 = w 3) :
∃ cost : Nat,
HaltsExactly (restoreInputs L)
((restoreInputs L).startCfg (roundState L T c w)) cost true ∧
(((restoreInputs L).step^[cost])
((restoreInputs L).startCfg (roundState L T c w))).tape =
roundState L T c V := by
classical
have step : ∀ (u : Fin 4 → Tape) (i : Fin 3) (j : Fin 4),
u j = cellsTape (TapeSymbol.blank :: Ld j) [] →
∃ cost : Nat,
HaltsExactly (copyBack (L.src i) (L.dst j))
((copyBack (L.src i) (L.dst j)).startCfg (roundState L T c u))
cost true ∧
(((copyBack (L.src i) (L.dst j)).step^[cost])
((copyBack (L.src i) (L.dst j)).startCfg
(roundState L T c u))).tape =
roundState L T c (Function.update u j
(cellsTape (TapeSymbol.blank :: Ld j)
(xs i ++ [TapeSymbol.blank]))) := by
intro u i j hu
have hval : roundState L T c u (L.src i) =
cellsTape (TapeSymbol.blank :: Ls i)
(xs i ++ TapeSymbol.blank :: Rs i) := by
rw [roundState_other L T c u (L.src i) (hsc i)
(fun j' h => (hL.src_dst i j') h.symm)]
exact hsrc i
obtain ⟨cost, hh, htp⟩ :=
copyBack_spec_of (L.src i) (L.dst j) (hL.copy_ne i j) (xs i) (Ls i)
(Ld j) (Rs i) [] (roundState L T c u) (hnb i) hval
(by rw [roundState_dst L hL]; exact hu)
refine ⟨cost, hh, ?_⟩
rw [htp, ← hval, Function.update_eq_self]
simp only [List.drop_nil]
rw [roundState_update_dst L hL]
rfl
obtain ⟨d0, g0, s0⟩ := step w 0 0 (hw 0)
rw [← hV0] at s0
obtain ⟨d1, g1, s1⟩ := step (Function.update w 0 (V 0)) 1 1
(by rw [Function.update_of_ne (by decide)]; exact hw 1)
rw [← hV1] at s1
obtain ⟨d2, g2, s2⟩ :=
step (Function.update (Function.update w 0 (V 0)) 1 (V 1)) 2 2
(by
rw [Function.update_of_ne (by decide), Function.update_of_ne (by decide)]
exact hw 2)
rw [← hV2] at s2
have hlast : Function.update (Function.update
(Function.update w 0 (V 0)) 1 (V 1)) 2 (V 2) = V := by
funext j
fin_cases j <;> first | rfl | exact hV3.symm
rw [hlast] at s2
have cc1 := chainStepC g1 s1 g2
have cc0 := chainStepC g0 s0 cc1.1
refine ⟨_, cc0.1, ?_⟩
have hfin := cc0.2
rw [cc1.2] at hfin
have hfin' : ((restoreInputs L).step^[d0 + 1 + (d1 + 1 + d2)])
((restoreInputs L).startCfg (roundState L T c w)) = _ := hfin
rw [hfin']
show (((copyBack (L.src 2) (L.dst 2)).step^[d2])
((copyBack (L.src 2) (L.dst 2)).startCfg (roundState L T c
(Function.update (Function.update w 0 (V 0)) 1 (V 1))))).tape = _
rw [s2]
/-! ## What the delegate is handed -/
/-- The `j`-th working tape's content: the `j`-th input for `j < 3`, and the
offset run for `j = 3`. -/
def roundContent (xs : Fin 3 → List TapeSymbol) (m : Nat) (j : Fin 4) :
List TapeSymbol :=
if h : j.val < 3 then xs ⟨j.val, h⟩
else List.replicate m (TapeSymbol.bit true)
/-- The delegate's four tapes when the round hands over: each carries its run
with the head on the run's first cell. -/
def roundTapes (Ld : Fin 4 → List TapeSymbol) (xs : Fin 3 → List TapeSymbol)
(m : Nat) (j : Fin 4) : Tape :=
cellsTape (TapeSymbol.blank :: Ld j)
(roundContent xs m j ++ [TapeSymbol.blank])
/-! ## The round -/
set_option maxHeartbeats 4000000 in
/-- **One round of the offset scheduler.** From a clock carrying `A`
accumulated marks with its head past them, inputs at their origins and a
counter holding the offset, the round delegates to `M` on the three inputs and
`1^offset`, and halts with `M`'s verdict. The final tapes are the delegate's,
in place, over a clock that has grown by the delegate's running time — the
same shape this theorem's own hypotheses read, so rounds compose. -/
theorem offsetRound_spec {states : Nat} (L : RoundLayout n) (hL : L.Wf)
(hsc : ∀ i, L.src i ≠ L.clk) (M : Machine 4 states) (T : Fin n → Tape)
(A : Nat) (Lclk : List TapeSymbol) (xs Ls Rs : Fin 3 → List TapeSymbol)
(cnt Lcnt Rcnt : List TapeSymbol) (Ld : Fin 4 → List TapeSymbol)
(Tm : Nat) (v : Bool)
(hxs : ∀ i, ∀ x ∈ xs i, x ≠ TapeSymbol.blank)
(hcm : ∀ x ∈ cnt, x ≠ TapeSymbol.blank)
(hclk : T L.clk = cellsTape
(List.replicate A (TapeSymbol.bit true) ++ TapeSymbol.blank :: Lclk) [])
(hsrc : ∀ i, T (L.src i) =
cellsTape (TapeSymbol.blank :: Ls i) (xs i ++ TapeSymbol.blank :: Rs i))
(hcnt : T L.cnt =
cellsTape (TapeSymbol.blank :: Lcnt) (cnt ++ TapeSymbol.blank :: Rcnt))
(hdst : ∀ j, ((moveDir HeadMove.right)^[A + A]) (T (L.dst j)) =
cellsTape (TapeSymbol.blank :: Ld j) [])
(hlive : ∀ m, m < Tm → M.result
((M.step^[m]) ⟨M.start, roundTapes Ld xs cnt.length⟩).state = none)
(hhalt : M.result
((M.step^[Tm]) ⟨M.start, roundTapes Ld xs cnt.length⟩).state = some v) :
∃ cost : Nat,
HaltsExactly (offsetRound L M) ((offsetRound L M).startCfg T) cost v ∧
(((offsetRound L M).step^[cost]) ((offsetRound L M).startCfg T)).tape =
clockTapesL L.sel L.clk T
((M.step^[Tm]) ⟨M.start, roundTapes Ld xs cnt.length⟩).tape
(roundClockLeft A Lclk) Tm := by
classical
have hnbC : ∀ x ∈ List.replicate A (TapeSymbol.bit true),
x ≠ TapeSymbol.blank := by
intro x hx
rw [List.eq_of_mem_replicate hx]
simp
-- 1. the clock goes back to its first mark
obtain ⟨g1, s1⟩ :=
rewindRun_spec L.clk (List.replicate A (TapeSymbol.bit true)) Lclk []
TapeSymbol.blank T hnbC (by rw [hclk, List.reverse_replicate]; rfl)
rw [roundState_start L hL] at s1
-- 2. every working tape is advanced past the previous round's garbage
obtain ⟨c2, g2, s2⟩ :=
advanceAll_spec L hL A Lclk [] T
(cellsTape (TapeSymbol.blank :: Lclk)
(List.replicate A (TapeSymbol.bit true) ++ TapeSymbol.blank :: []))
(fun j => T (L.dst j)) (fun j => cellsTape (TapeSymbol.blank :: Ld j) [])
rfl hdst
-- 3. the inputs are restored
obtain ⟨c3, g3, s3⟩ :=
restoreInputs_spec L hL hsc T
(cellsTape (TapeSymbol.blank :: Lclk)
(List.replicate A (TapeSymbol.bit true) ++ TapeSymbol.blank :: []))
(fun j => cellsTape (TapeSymbol.blank :: Ld j) [])
(Function.update (roundTapes Ld xs cnt.length) 3
(cellsTape (TapeSymbol.blank :: Ld 3) []))
xs Ls Rs Ld hxs hsrc (fun _ => rfl) rfl rfl rfl rfl
-- 4. the offset run is written from the counter
have hcntv : roundState L T
(cellsTape (TapeSymbol.blank :: Lclk)
(List.replicate A (TapeSymbol.bit true) ++ TapeSymbol.blank :: []))
(Function.update (roundTapes Ld xs cnt.length) 3
(cellsTape (TapeSymbol.blank :: Ld 3) [])) L.cnt =
cellsTape (TapeSymbol.blank :: Lcnt)
(cnt ++ TapeSymbol.blank :: Rcnt) := by
rw [roundState_other _ _ _ _ L.cnt (fun h => hL.clk_cnt h.symm) hL.cnt_dst]
exact hcnt
obtain ⟨c4, g4, s4⟩ :=
markBack_spec L.cnt (L.dst 3) (hL.mark_ne 3) cnt Lcnt (Ld 3) Rcnt []
(roundState L T
(cellsTape (TapeSymbol.blank :: Lclk)
(List.replicate A (TapeSymbol.bit true) ++ TapeSymbol.blank :: []))
(Function.update (roundTapes Ld xs cnt.length) 3
(cellsTape (TapeSymbol.blank :: Ld 3) [])))
hcm hcntv (by rw [roundState_dst L hL]; rfl)
rw [← hcntv, Function.update_eq_self] at s4
rw [show (([] : List TapeSymbol).drop cnt.length).headD TapeSymbol.blank ::
(([] : List TapeSymbol).drop cnt.length).tail = [TapeSymbol.blank]
from by simp] at s4
rw [roundState_update_dst L hL,
show Function.update
(Function.update (roundTapes Ld xs cnt.length) 3
(cellsTape (TapeSymbol.blank :: Ld 3) [])) 3
(cellsTape (TapeSymbol.blank :: Ld 3)
(List.replicate cnt.length (TapeSymbol.bit true) ++
[TapeSymbol.blank])) = roundTapes Ld xs cnt.length
from by funext j; fin_cases j <;> rfl] at s4
-- 5. the clock returns to virgin tape
obtain ⟨c5, g5, s5⟩ :=
clockScan_spec L.clk A Lclk
(roundState L T
(cellsTape (TapeSymbol.blank :: Lclk)
(List.replicate A (TapeSymbol.bit true) ++ TapeSymbol.blank :: []))
(roundTapes Ld xs cnt.length))
(by rw [roundState_clk])
rw [roundState_update_clk, roundState_clockTapesL] at s5
-- 6. the delegate runs
obtain ⟨g6, s6⟩ :=
embedClockL_spec L.sel L.clk hL.sel_inj hL.sel_clk M T
(roundTapes Ld xs cnt.length) (roundClockLeft A Lclk) Tm v hlive hhalt
have k5 := chainStepC g5 s5 g6
have k4 := chainStepC g4 s4 k5.1
have k3 := chainStepC g3 s3 k4.1
have k2 := chainStepC g2 s2 k3.1
have k1 := chainStepC g1 s1 k2.1
refine ⟨_, k1.1, ?_⟩
have hfin := k1.2
rw [k2.2, k3.2, k4.2, k5.2] at hfin
have hfin' : ((offsetRound L M).step^[_])
((offsetRound L M).startCfg T) = _ := hfin
rw [hfin']
show (((embedClock L.sel L.clk M).step^[Tm])
((embedClock L.sel L.clk M).startCfg
(clockTapesL L.sel L.clk T (roundTapes Ld xs cnt.length)
(roundClockLeft A Lclk) 0))).tape = _
rw [s6]
/-- The round needs one distinctness fact `RoundLayout.Wf` does not carry: the
first stage rewrites the clock, so an input tape that *were* the clock would no
longer be at its origin when stage three copies it. The standard layout has
it. -/
theorem stdLayout_src_clk : ∀ i, stdLayout.src i ≠ stdLayout.clk := by
intro i hc
have := congrArg Fin.val hc
simp [stdLayout] at this
omega
end Round
end SipserGacsLautemann