The round's cost
Definitionsgl_round_costThe round's cost. offsetRound_spec said the round halts; it did not say how quickly. The loop built on it must run in polynomial time, and a halting cost cannot be recovered after the fact — so the bound is threaded through the same proof here, before the loop rather than after.
A round costs at most , where is the clock's accumulated marks and the delegated run's length: linear in everything it touches, which is what will keep the loop quadratic overall.
copyBack_spec_ofB and clockScan_specB had to be fresh bounded copies rather than corollaries. The first is a consequence of the defect reported earlier — the published copy specification carries a hypothesis that is unsatisfiable inside a round, so the bounded restatement built on it inherits the flaw and a second copy is needed. That is worth stating plainly: an unusable hypothesis does not stay contained; it propagates into everything derived downstream, and the cost of leaving it in place grows with each layer.
import Definitions.Def_sgl_stage_costs
/-!
# The round's cost
`offsetRound_spec` says the round halts; it does not say how quickly. The
loop built on it must run in polynomial time, and a halting cost cannot be
recovered after the fact — so the bound is threaded through the same proof
here, before the loop rather than after.
`copyBack_spec_ofB` is the copy stage's bounded form. It has to be a fresh
copy rather than a corollary of `copyBack_specB`, because the published
`copyBack_spec` carries a hypothesis that is unsatisfiable in a round; that
defect propagates into every bounded restatement built on it.
-/
namespace SipserGacsLautemann
section Round
variable {n : Nat}
theorem copyBack_spec_ofB {tapes : Nat} (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, cost ≤ 13 * cs.length + 16 ∧
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)),
by omega, ?_, ?_⟩
· 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
theorem clockScan_specB {tapes : Nat} (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, cost ≤ 4 * A + 3 ∧
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, by omega, 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, by omega, 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
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_specB (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, cost ≤ 72 * A + 87 ∧
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, cost ≤ 18 * A + 21 ∧
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, hb, hh, htp⟩ :=
skipAhead_specB 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, by simpa using hb, hh, ?_⟩
rw [htp, roundState_dst L hL, List.length_replicate,
roundState_update_dst L hL]
obtain ⟨c0, b0, h0, t0⟩ := step w 0
rw [hV 0] at t0
obtain ⟨c1, b1, 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, b2, 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, b3, 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 ⟨c0 + 1 + (c1 + 1 + (c2 + 1 + c3)), by omega, 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_specB (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,
cost ≤ 13 * ((xs 0).length + (xs 1).length + (xs 2).length) + 50 ∧
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, cost ≤ 13 * (xs i).length + 16 ∧
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, hb, hh, htp⟩ :=
copyBack_spec_ofB (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, hb, hh, ?_⟩
rw [htp, ← hval, Function.update_eq_self]
simp only [List.drop_nil]
rw [roundState_update_dst L hL]
rfl
obtain ⟨d0, e0, g0, s0⟩ := step w 0 0 (hw 0)
rw [← hV0] at s0
obtain ⟨d1, e1, 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, e2, 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 ⟨d0 + 1 + (d1 + 1 + d2), by omega, 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 -/
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_specB {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,
cost ≤ 80 * A + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
+ 13 * cnt.length + Tm + 170 ∧
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, b2, g2, s2⟩ :=
advanceAll_specB 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, b3, g3, s3⟩ :=
restoreInputs_specB 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, b4, g4, s4⟩ :=
markBack_specB 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, b5, g5, s5⟩ :=
clockScan_specB 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 ⟨(List.replicate A (TapeSymbol.bit true)).length * 4 + 3 + 1 + 1 + 1 +
(c2 + 1 + (c3 + 1 + (c4 + 1 + (c5 + 1 + Tm)))),
by simp only [List.length_replicate] at b4 ⊢; omega, k1.1, ?_⟩
have hfin := k1.2
rw [k2.2, k3.2, k4.2, k5.2] at hfin
have hfin' : ((offsetRound L M).step^[
(List.replicate A (TapeSymbol.bit true)).length * 4 + 3 + 1 + 1 + 1 +
(c2 + 1 + (c3 + 1 + (c4 + 1 + (c5 + 1 + Tm))))])
((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]
end Round
end SipserGacsLautemann