sgl_prologue_cost
DefinitionDefinition code
import Definitions.Def_sgl_dig_costs
/-!
# What the prologue costs, end to end
The clock's stage is two marks and three tallies; the prologue is three inputs,
two origin markers, the clock and the guide. Everything underneath now reports
an exact cost, so both totals are linear in the inputs' lengths and the bounds
are arithmetic.
The prologue's bound is deliberately loose. It is a one-time linear cost
against a scheduler whose own bound is a product of the round count and the
delegate's time, so nothing is gained by tightening it, and a slack bound is
one less thing to re-derive if a stage changes.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
set_option maxHeartbeats 4000000 in
/-- **The clock's stage costs `9Σ|x| + 36`.** -/
theorem clockSetup_specB (s0 s1 s2 clk : Fin tapes)
(h0 : s0 ≠ clk) (h1 : s1 ≠ clk) (h2 : s2 ≠ clk)
(x0 x1 x2 L0 L1 L2 R0 R1 R2 : List TapeSymbol) (T : Fin tapes → Tape)
(hn0 : ∀ c ∈ x0, c ≠ TapeSymbol.blank)
(hn1 : ∀ c ∈ x1, c ≠ TapeSymbol.blank)
(hn2 : ∀ c ∈ x2, c ≠ TapeSymbol.blank)
(hs0 : T s0 = cellsTape (TapeSymbol.blank :: L0)
(x0 ++ TapeSymbol.blank :: R0))
(hs1 : T s1 = cellsTape (TapeSymbol.blank :: L1)
(x1 ++ TapeSymbol.blank :: R1))
(hs2 : T s2 = cellsTape (TapeSymbol.blank :: L2)
(x2 ++ TapeSymbol.blank :: R2))
(hclk : T clk = cellsTape [TapeSymbol.blank] []) :
∃ cost : Nat,
cost ≤ 9 * (x0.length + x1.length + x2.length) + 36 ∧
HaltsExactly (clockSetup s0 s1 s2 clk)
((clockSetup s0 s1 s2 clk).startCfg T) cost true ∧
(((clockSetup s0 s1 s2 clk).step^[cost])
((clockSetup s0 s1 s2 clk).startCfg T)).tape =
Function.update T clk
(cellsTape (List.replicate
(x2.length + (x1.length + (x0.length + 2))) (TapeSymbol.bit true)
++ [TapeSymbol.blank]) []) := by
classical
obtain ⟨gA, sA⟩ := writeMark_spec clk [TapeSymbol.blank] [] T hclk
set TA := Function.update T clk
(cellsTape (TapeSymbol.bit true :: [TapeSymbol.blank])
([] : List TapeSymbol).tail) with hTA
have hTAclk : TA clk = cellsTape
(List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] := by
rw [hTA, Function.update_self]
simp
obtain ⟨gB, sB⟩ := writeMark_spec clk
(List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] TA hTAclk
set TB := Function.update TA clk
(cellsTape (TapeSymbol.bit true ::
(List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]))
([] : List TapeSymbol).tail) with hTB
have hTBclk : TB clk = cellsTape
(List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] := by
rw [hTB, Function.update_self]
simp [List.replicate_succ]
have hTBs : ∀ (s : Fin tapes), s ≠ clk → TB s = T s := by
intro s hs
rw [hTB, Function.update_of_ne hs, hTA, Function.update_of_ne hs]
obtain ⟨c1, hb1, g1, t1⟩ := tallyOnto_specB s0 clk h0 x0 L0 R0
(List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] TB hn0
(by rw [hTBs s0 h0]; exact hs0) hTBclk
set T1 := Function.update TB clk
(cellsTape (List.replicate x0.length (TapeSymbol.bit true) ++
(List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]))
(([] : List TapeSymbol).drop x0.length)) with hT1
have hT1clk : T1 clk = cellsTape
(List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) [] := by
rw [hT1, Function.update_self, ← List.append_assoc, ← List.replicate_add]
simp
have hT1s : ∀ (s : Fin tapes), s ≠ clk → T1 s = T s := by
intro s hs
rw [hT1, Function.update_of_ne hs]
exact hTBs s hs
obtain ⟨c2, hb2, g2, t2⟩ := tallyOnto_specB s1 clk h1 x1 L1 R1
(List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) [] T1 hn1
(by rw [hT1s s1 h1]; exact hs1) hT1clk
set T2 := Function.update T1 clk
(cellsTape (List.replicate x1.length (TapeSymbol.bit true) ++
(List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
[TapeSymbol.blank]))
(([] : List TapeSymbol).drop x1.length)) with hT2
have hT2clk : T2 clk = cellsTape
(List.replicate (x1.length + (x0.length + 2)) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) [] := by
rw [hT2, Function.update_self, ← List.append_assoc, ← List.replicate_add]
simp
have hT2s : ∀ (s : Fin tapes), s ≠ clk → T2 s = T s := by
intro s hs
rw [hT2, Function.update_of_ne hs]
exact hT1s s hs
obtain ⟨c3, hb3, g3, t3⟩ := tallyOnto_specB s2 clk h2 x2 L2 R2
(List.replicate (x1.length + (x0.length + 2)) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) [] T2 hn2
(by rw [hT2s s2 h2]; exact hs2) hT2clk
have k3 := chainStepC g2 t2 g3
have k2 := chainStepC g1 t1 k3.1
have k1 := chainStepC gB sB k2.1
have k0 := chainStepC gA sA k1.1
refine ⟨_, by omega, k0.1, ?_⟩
have hfin := k0.2
rw [k1.2, k2.2, k3.2] at hfin
have hfin' : ((clockSetup s0 s1 s2 clk).step^[_])
((clockSetup s0 s1 s2 clk).startCfg T) = _ := hfin
rw [hfin']
show (((tallyOnto s2 clk).step^[c3])
((tallyOnto s2 clk).startCfg T2)).tape = _
rw [t3]
funext j
by_cases hj : j = clk
· subst hj
rw [Function.update_self, Function.update_self, ← List.append_assoc,
← List.replicate_add]
simp
· rw [Function.update_of_ne hj, Function.update_of_ne hj]
exact hT2s j hj
set_option maxHeartbeats 4000000 in
/-- **The prologue is linear in its inputs.** -/
theorem prologue_specB (idx : Fin 7 → Fin tapes) (hinj : Function.Injective idx)
(x0 x1 x2 : List TapeSymbol) (T : Fin tapes → Tape)
(hn0 : ∀ c ∈ x0, c ≠ TapeSymbol.blank)
(hn1 : ∀ c ∈ x1, c ≠ TapeSymbol.blank)
(hn2 : ∀ c ∈ x2, c ≠ TapeSymbol.blank)
(hx0 : T (idx 0) = cellsTape [] x0)
(hx1 : T (idx 1) = cellsTape [] x1)
(hx2 : T (idx 2) = cellsTape [] x2)
(hclk : T (idx 3) = cellsTape [] [])
(hgd : T (idx 4) = cellsTape [] [])
(hcnt : T (idx 5) = cellsTape [] []) :
∃ cost : Nat, ∃ T' : Fin tapes → Tape,
cost ≤ 50 * (x0.length + x1.length + x2.length) + 200 ∧
HaltsExactly (prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
(idx 6))
((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
(idx 6)).startCfg T) cost true ∧
(((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
(idx 6)).step^[cost])
((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
(idx 6)).startCfg T)).tape = T' ∧
T' (idx 0) = cellsTape [TapeSymbol.blank] (x0 ++ [TapeSymbol.blank]) ∧
T' (idx 1) = cellsTape [TapeSymbol.blank] (x1 ++ [TapeSymbol.blank]) ∧
T' (idx 2) = cellsTape [TapeSymbol.blank] (x2 ++ [TapeSymbol.blank]) ∧
T' (idx 3) = cellsTape (List.replicate
(x2.length + (x1.length + (x0.length + 2))) (TapeSymbol.bit true)
++ [TapeSymbol.blank]) [] ∧
T' (idx 4) = cellsTape []
(List.replicate (x2.length + 1) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) ∧
T' (idx 5) = cellsTape
(List.replicate (x2.length + 2) TapeSymbol.blank) [] ∧
(∀ j, j ≠ idx 0 → j ≠ idx 1 → j ≠ idx 2 → j ≠ idx 3 → j ≠ idx 4 →
j ≠ idx 5 → T' j = T j) := by
classical
have hne : ∀ a b : Fin 7, a ≠ b → idx a ≠ idx b :=
fun a b hab h => hab (hinj h)
-- 1..3: the inputs
obtain ⟨c1, hb1, g1, t1⟩ := inputPrep_specB (idx 0) (idx 6) (hne 0 6 (by decide))
x0 T hn0 hx0
set T1 := Function.update T (idx 0)
(cellsTape [TapeSymbol.blank] (x0 ++ [TapeSymbol.blank])) with hT1
obtain ⟨c2, hb2, g2, t2⟩ := inputPrep_specB (idx 1) (idx 6) (hne 1 6 (by decide))
x1 T1 hn1 (by rw [hT1, Function.update_of_ne (hne 1 0 (by decide))]; exact hx1)
set T2 := Function.update T1 (idx 1)
(cellsTape [TapeSymbol.blank] (x1 ++ [TapeSymbol.blank])) with hT2
obtain ⟨c3, hb3, g3, t3⟩ := inputPrep_specB (idx 2) (idx 6) (hne 2 6 (by decide))
x2 T2 hn2 (by
rw [hT2, Function.update_of_ne (hne 2 1 (by decide)), hT1,
Function.update_of_ne (hne 2 0 (by decide))]
exact hx2)
set T3 := Function.update T2 (idx 2)
(cellsTape [TapeSymbol.blank] (x2 ++ [TapeSymbol.blank])) with hT3
have hT3o : ∀ j, j ≠ idx 0 → j ≠ idx 1 → j ≠ idx 2 → T3 j = T j := by
intro j h0 h1 h2
rw [hT3, Function.update_of_ne h2, hT2, Function.update_of_ne h1, hT1,
Function.update_of_ne h0]
-- 4, 5: the origin markers
obtain ⟨g4, t4⟩ := prepTape_spec (idx 3) T3 []
(by rw [hT3o (idx 3) (hne 3 0 (by decide)) (hne 3 1 (by decide))
(hne 3 2 (by decide))]; exact hclk)
set T4 := Function.update T3 (idx 3)
(cellsTape [TapeSymbol.blank] ([] : List TapeSymbol)) with hT4
obtain ⟨g5, t5⟩ := prepTape_spec (idx 4) T4 []
(by
rw [hT4, Function.update_of_ne (hne 4 3 (by decide)),
hT3o (idx 4) (hne 4 0 (by decide)) (hne 4 1 (by decide))
(hne 4 2 (by decide))]
exact hgd)
set T5 := Function.update T4 (idx 4)
(cellsTape [TapeSymbol.blank] ([] : List TapeSymbol)) with hT5
have h5x0 : T5 (idx 0) =
cellsTape [TapeSymbol.blank] (x0 ++ [TapeSymbol.blank]) := by
rw [hT5, Function.update_of_ne (hne 0 4 (by decide)), hT4,
Function.update_of_ne (hne 0 3 (by decide)), hT3,
Function.update_of_ne (hne 0 2 (by decide)), hT2,
Function.update_of_ne (hne 0 1 (by decide)), hT1, Function.update_self]
have h5x1 : T5 (idx 1) =
cellsTape [TapeSymbol.blank] (x1 ++ [TapeSymbol.blank]) := by
rw [hT5, Function.update_of_ne (hne 1 4 (by decide)), hT4,
Function.update_of_ne (hne 1 3 (by decide)), hT3,
Function.update_of_ne (hne 1 2 (by decide)), hT2, Function.update_self]
have h5x2 : T5 (idx 2) =
cellsTape [TapeSymbol.blank] (x2 ++ [TapeSymbol.blank]) := by
rw [hT5, Function.update_of_ne (hne 2 4 (by decide)), hT4,
Function.update_of_ne (hne 2 3 (by decide)), hT3, Function.update_self]
have h5clk : T5 (idx 3) = cellsTape [TapeSymbol.blank] [] := by
rw [hT5, Function.update_of_ne (hne 3 4 (by decide)), hT4,
Function.update_self]
have h5gd : T5 (idx 4) = cellsTape [TapeSymbol.blank] [] := by
rw [hT5, Function.update_self]
have h5cnt : T5 (idx 5) = cellsTape [] [] := by
rw [hT5, Function.update_of_ne (hne 5 4 (by decide)), hT4,
Function.update_of_ne (hne 5 3 (by decide)),
hT3o (idx 5) (hne 5 0 (by decide)) (hne 5 1 (by decide))
(hne 5 2 (by decide))]
exact hcnt
have h5o : ∀ j, j ≠ idx 0 → j ≠ idx 1 → j ≠ idx 2 → j ≠ idx 3 → j ≠ idx 4 →
T5 j = T j := by
intro j h0 h1 h2 h3 h4
rw [hT5, Function.update_of_ne h4, hT4, Function.update_of_ne h3,
hT3o j h0 h1 h2]
-- 6: the clock
obtain ⟨c6, hb6, g6, t6⟩ := clockSetup_specB (idx 0) (idx 1) (idx 2) (idx 3)
(hne 0 3 (by decide)) (hne 1 3 (by decide)) (hne 2 3 (by decide))
x0 x1 x2 [] [] [] [] [] [] T5 hn0 hn1 hn2 h5x0 h5x1 h5x2 h5clk
set T6 := Function.update T5 (idx 3)
(cellsTape (List.replicate (x2.length + (x1.length + (x0.length + 2)))
(TapeSymbol.bit true) ++ [TapeSymbol.blank]) []) with hT6
-- 7: the guide and the counter
obtain ⟨c7, hb7, g7, t7⟩ := guideSetup_specB (idx 2) (idx 4) (idx 5)
(hne 2 4 (by decide)) (hne 4 5 (by decide)) (hne 2 5 (by decide))
x2 [] [] T6 hn2
(by rw [hT6, Function.update_of_ne (hne 2 3 (by decide))]; exact h5x2)
(by rw [hT6, Function.update_of_ne (hne 4 3 (by decide))]; exact h5gd)
(by rw [hT6, Function.update_of_ne (hne 5 3 (by decide))]; exact h5cnt)
set T7 := Function.update (Function.update T6 (idx 5)
(cellsTape (List.replicate (x2.length + 2) TapeSymbol.blank) []))
(idx 4) (cellsTape []
(List.replicate (x2.length + 1) (TapeSymbol.bit true) ++
[TapeSymbol.blank])) with hT7
-- the chain
have p6 := chainStepC g6 t6 g7
have p5 := chainStepC g5 t5 p6.1
have p4 := chainStepC g4 t4 p5.1
have p3 := chainStepC g3 t3 p4.1
have p2 := chainStepC g2 t2 p3.1
have p1 := chainStepC g1 t1 p2.1
have hIR : ∀ {S₁ S₂ : Type} (b : Bool) (c : TypedConfiguration tapes S₂),
(TypedConfiguration.inRight (S₁ := S₁) b c).tape = c.tape :=
fun _ _ => rfl
refine ⟨_, T7, by omega, p1.1, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
· have hfin : ((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
(idx 6)).step^[_])
((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
(idx 6)).startCfg T) = _ := p1.2
rw [hfin, hIR, p2.2, hIR, p3.2, hIR, p4.2, hIR, p5.2, hIR, p6.2, hIR, t7]
· rw [hT7, Function.update_of_ne (hne 0 4 (by decide)),
Function.update_of_ne (hne 0 5 (by decide)), hT6,
Function.update_of_ne (hne 0 3 (by decide))]
exact h5x0
· rw [hT7, Function.update_of_ne (hne 1 4 (by decide)),
Function.update_of_ne (hne 1 5 (by decide)), hT6,
Function.update_of_ne (hne 1 3 (by decide))]
exact h5x1
· rw [hT7, Function.update_of_ne (hne 2 4 (by decide)),
Function.update_of_ne (hne 2 5 (by decide)), hT6,
Function.update_of_ne (hne 2 3 (by decide))]
exact h5x2
· rw [hT7, Function.update_of_ne (hne 3 4 (by decide)),
Function.update_of_ne (hne 3 5 (by decide)), hT6, Function.update_self]
· rw [hT7, Function.update_self]
· rw [hT7, Function.update_of_ne (hne 5 4 (by decide)),
Function.update_self]
· intro j h0 h1 h2 h3 h4 h5
rw [hT7, Function.update_of_ne h4, Function.update_of_ne h5, hT6,
Function.update_of_ne h3]
exact h5o j h0 h1 h2 h3 h4
end SipserGacsLautemann