Explicit costs for the round's stages
Definitionsgl_stage_costsExplicit costs for the round's stages. Three stage specifications concluded with no bound — enough for correctness, useless for complexity.
The loop built on them has to run in polynomial time, and as the dilation taught this development, a halting cost cannot be bounded after the fact: HaltsExactly pins the time, so recovering an inequality about it means re-deriving it. Doing that after the loop was built would mean proving the loop twice. So the bounds are threaded through the same proofs here, first.
Copying a run and returning both heads costs at most ; writing a counter's worth of marks the same; a skip, which is two passes rather than one, at most . Each proof already produced a concrete value — the change is that the value is now named and bounded rather than hidden behind an existential.
All three compiled on the first attempt, which is some evidence the bounds are the natural ones rather than padding.
import Definitions.Def_sgl_round_spec
/-!
# Explicit costs for the round's stages
Three stage specifications concluded `∃ cost, …` with no bound. That is
enough for correctness and useless for complexity: the loop built on them must
run in polynomial time, and — as the dilation taught this development — a
halting cost cannot be bounded after the fact, because `HaltsExactly` pins the
time and recovering an inequality about it means re-deriving it.
So the bound is threaded through the same proofs here, before the loop is
built rather than after. Each proof already produced a concrete value; what
changes is that the value is now named and bounded instead of hidden behind an
existential.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
set_option maxHeartbeats 4000000 in
/-- **Restore a tape from another.** The source is left exactly as it was;
the target now carries the same run, both heads on its first cell. -/
theorem copyBack_specB (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)
(hlen : cs.length ≤ Rt.length) :
∃ 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
-- the copy
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
-- rewind the source
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
-- rewind the target
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
set_option maxHeartbeats 4000000 in
/-- **Build the offset tape.** The counter is restored exactly; the worker
gains a run of marks as long as the counter's, both heads on its first cell. -/
theorem markBack_specB (c w : Fin tapes) (hcw : c ≠ w)
(marks : List TapeSymbol) (Lc Lw Rc Rw : List TapeSymbol)
(T : Fin tapes → Tape)
(hnb : ∀ x ∈ marks, x ≠ TapeSymbol.blank)
(hc : T c = cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc))
(hw : T w = cellsTape (TapeSymbol.blank :: Lw) Rw) :
∃ cost : Nat, cost ≤ 13 * marks.length + 16 ∧
HaltsExactly (markBack c w) ((markBack c w).startCfg T) cost true ∧
(((markBack c w).step^[cost]) ((markBack c w).startCfg T)).tape =
Function.update (Function.update T c
(cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc))) w
(cellsTape (TapeSymbol.blank :: Lw)
(List.replicate marks.length (TapeSymbol.bit true) ++
(Rw.drop marks.length).headD TapeSymbol.blank ::
(Rw.drop marks.length).tail)) := by
classical
set G := guidedStep c w HeadMove.right (some (TapeSymbol.bit true)) with hG
obtain ⟨hia, hib⟩ := guidedStep_write_iterate c w hcw marks T
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc)
(TapeSymbol.blank :: Lw) Rw (by rw [hc]) (by rw [hw])
-- the walk
obtain ⟨hW, hWt⟩ := guidedWalk_spec c w hcw HeadMove.right
(some (TapeSymbol.bit true)) marks.length T
(guidedStep_write_marks c w hcw marks T (TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) (TapeSymbol.blank :: Lw) Rw hnb
(by rw [hc]) (by rw [hw]))
(by rw [hia]; rfl)
set T1 := ((G)^[marks.length]) T with hT1
have hT1c : T1 c = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) := hia
have hT1w : T1 w =
cellsTape (List.replicate marks.length (TapeSymbol.bit true) ++
TapeSymbol.blank :: Lw) (Rw.drop marks.length) := hib
-- rewind the counter
obtain ⟨hRc, hRct⟩ := rewindRun_spec c marks Lc Rc TapeSymbol.blank T1
hnb (by rw [hT1c])
set T2 := Function.update T1 c
(cellsTape (TapeSymbol.blank :: Lc) (marks ++ TapeSymbol.blank :: Rc))
with hT2
have hT2w : T2 w =
cellsTape (List.replicate marks.length (TapeSymbol.bit true) ++
TapeSymbol.blank :: Lw) (Rw.drop marks.length) := by
rw [hT2, Function.update_of_ne (fun h => hcw h.symm)]
exact hT1w
-- rewind the worker
have hrep : ∀ x ∈ List.replicate marks.length (TapeSymbol.bit true),
x ≠ TapeSymbol.blank := by
intro x hx
rw [List.eq_of_mem_replicate hx]
simp
obtain ⟨hRw, hRwt⟩ := rewindRun_spec w
(List.replicate marks.length (TapeSymbol.bit true)) Lw
((Rw.drop marks.length).tail)
((Rw.drop marks.length).headD TapeSymbol.blank) T2 hrep
(by
rw [hT2w]
rw [show (List.replicate marks.length (TapeSymbol.bit true)).reverse =
List.replicate marks.length (TapeSymbol.bit true) by
simp [List.reverse_replicate]]
exact cellsTape_norm _ _)
refine ⟨(marks.length * 5 + 4) + 1 +
((marks.length * 4 + 3 + 1 + 1) + 1 +
((List.replicate marks.length (TapeSymbol.bit true)).length * 4
+ 3 + 1 + 1)),
by simp; omega, (chainStepC hW hWt (chainStepC hRc hRct hRw).1).1, ?_⟩
have hch := chainStepC hW hWt (chainStepC hRc hRct hRw).1
have hin := chainStepC hRc hRct hRw
have hfin := hch.2
rw [hin.2] at hfin
have hfin' : ((markBack c w).step^[(marks.length * 5 + 4) + 1 +
((marks.length * 4 + 3 + 1 + 1) + 1 +
((List.replicate marks.length (TapeSymbol.bit true)).length * 4
+ 3 + 1 + 1))])
((markBack c w).startCfg T) = _ := hfin
rw [hfin']
show (((rewindRun w).step^[
(List.replicate marks.length (TapeSymbol.bit true)).length * 4 + 3 + 1 + 1])
((rewindRun w).startCfg T2)).tape = _
rw [hRwt, hT2]
funext j
by_cases hj : j = w
· subst hj; simp
· rw [Function.update_of_ne hj, Function.update_of_ne hj]
by_cases hj2 : j = c
· subst hj2; simp
· rw [Function.update_of_ne hj2, Function.update_of_ne hj2, hT1]
exact guidedStep_other c w HeadMove.right (some (TapeSymbol.bit true))
marks.length T j hj2 hj
set_option maxHeartbeats 4000000 in
/-- **Advance the worker by twice the clock's marks, clock restored.** -/
theorem skipAhead_specB (clk w : Fin tapes) (hcw : clk ≠ w)
(marks Lc Rc : List TapeSymbol) (T : Fin tapes → Tape)
(hnb : ∀ x ∈ marks, x ≠ TapeSymbol.blank)
(hc : T clk = cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc)) :
∃ cost : Nat, cost ≤ 18 * marks.length + 21 ∧
HaltsExactly (skipAhead clk w) ((skipAhead clk w).startCfg T) cost true ∧
(((skipAhead clk w).step^[cost])
((skipAhead clk w).startCfg T)).tape =
Function.update T w
(((moveDir HeadMove.right)^[marks.length + marks.length]) (T w)) := by
classical
set G := guidedStep clk w HeadMove.right none with hG
-- first pass
obtain ⟨h1a, h1b⟩ := guidedStep_skip_iterate clk w hcw marks T
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hc])
obtain ⟨hW1, hW1t⟩ := guidedWalk_spec clk w hcw HeadMove.right none
marks.length T
(guidedStep_skip_marks clk w hcw marks T (TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) hnb (by rw [hc]))
(by rw [h1a]; rfl)
set T1 := (G^[marks.length]) T with hT1
have hT1c : T1 clk = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) := h1a
have hT1w : T1 w = ((moveDir HeadMove.right)^[marks.length]) (T w) := h1b
-- first rewind
obtain ⟨hR1, hR1t⟩ := rewindRun_spec clk marks Lc Rc TapeSymbol.blank T1
hnb (by rw [hT1c])
set T2 := Function.update T1 clk
(cellsTape (TapeSymbol.blank :: Lc) (marks ++ TapeSymbol.blank :: Rc))
with hT2
have hT2c : T2 clk = cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc) := by rw [hT2]; simp
have hT2w : T2 w = ((moveDir HeadMove.right)^[marks.length]) (T w) := by
rw [hT2, Function.update_of_ne (fun h => hcw h.symm)]
exact hT1w
-- second pass
obtain ⟨h2a, h2b⟩ := guidedStep_skip_iterate clk w hcw marks T2
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hT2c])
obtain ⟨hW2, hW2t⟩ := guidedWalk_spec clk w hcw HeadMove.right none
marks.length T2
(guidedStep_skip_marks clk w hcw marks T2 (TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) hnb (by rw [hT2c]))
(by rw [h2a]; rfl)
set T3 := (G^[marks.length]) T2 with hT3
have hT3c : T3 clk = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) := h2a
-- second rewind
obtain ⟨hR2, hR2t⟩ := rewindRun_spec clk marks Lc Rc TapeSymbol.blank T3
hnb (by rw [hT3c])
refine ⟨(marks.length * 5 + 4) + 1 + ((marks.length * 4 + 3 + 1 + 1) + 1 +
((marks.length * 5 + 4) + 1 + (marks.length * 4 + 3 + 1 + 1))),
by omega, (chainStepC hW1 hW1t (chainStepC hR1 hR1t
(chainStepC hW2 hW2t hR2).1).1).1, ?_⟩
have hin2 := chainStepC hW2 hW2t hR2
have hin1 := chainStepC hR1 hR1t hin2.1
have hch := chainStepC hW1 hW1t hin1.1
have hfin := hch.2
rw [hin1.2, hin2.2] at hfin
have hfin' : ((skipAhead clk w).step^[(marks.length * 5 + 4) + 1 +
((marks.length * 4 + 3 + 1 + 1) + 1 +
((marks.length * 5 + 4) + 1 + (marks.length * 4 + 3 + 1 + 1)))])
((skipAhead clk w).startCfg T) = _ := hfin
rw [hfin']
show (((rewindRun clk).step^[marks.length * 4 + 3 + 1 + 1])
((rewindRun clk).startCfg T3)).tape = _
rw [hR2t]
funext j
by_cases hj : j = clk
· subst hj
rw [Function.update_self, Function.update_of_ne hcw, hc]
· rw [Function.update_of_ne hj]
by_cases hj2 : j = w
· subst hj2
rw [Function.update_self, h2b, hT2w, ← Function.iterate_add_apply]
· rw [Function.update_of_ne hj2, hT3,
guidedStep_other clk w HeadMove.right none marks.length T2 j hj hj2,
hT2, Function.update_of_ne hj, hT1,
guidedStep_other clk w HeadMove.right none marks.length T j hj hj2]
end SipserGacsLautemann