sgl_dig_costs
DefinitionDefinition code
import Definitions.Def_sgl_walk_costs
/-!
# What the dig and the guide cost
The same restatement as the walk stages, for the three that build the counter's
reservoir and the guide. The excavation's round trip is two guided walks and
two rewinds, so `18m + 25`; the two extra steps on each side bring the
reservoir to `18m + 31`; and the guide's stage adds a tally and a bump on top.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
set_option maxHeartbeats 4000000 in
/-- **The excavation costs `18m + 25`.** -/
theorem digRoundTrip_specB (g w : Fin tapes) (hgw : g ≠ w)
(marks Lc Rc : List TapeSymbol) (T : Fin tapes → Tape)
(hnb : ∀ x ∈ marks, x ≠ TapeSymbol.blank)
(hc : T g = cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc)) :
∃ cost : Nat,
cost ≤ 18 * marks.length + 25 ∧
HaltsExactly (digRoundTrip g w) ((digRoundTrip g w).startCfg T) cost
true ∧
(((digRoundTrip g w).step^[cost])
((digRoundTrip g w).startCfg T)).tape =
Function.update T w
(((moveDir HeadMove.right)^[marks.length])
(((moveDir HeadMove.left)^[marks.length]) (T w))) := by
classical
obtain ⟨h1a, h1b⟩ := guidedStep_move_iterate g w hgw HeadMove.left marks T
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hc])
obtain ⟨hW1, hW1t⟩ := guidedWalk_spec g w hgw HeadMove.left none
marks.length T
(guidedStep_move_marks g w hgw HeadMove.left marks T
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) hnb (by rw [hc]))
(by rw [h1a]; rfl)
set T1 := ((guidedStep g w HeadMove.left none)^[marks.length]) T with hT1
have hT1c : T1 g = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) := h1a
have hT1w : T1 w = ((moveDir HeadMove.left)^[marks.length]) (T w) := h1b
obtain ⟨hR1, hR1t⟩ := rewindRun_spec g marks Lc Rc TapeSymbol.blank T1
hnb (by rw [hT1c])
set T2 := Function.update T1 g
(cellsTape (TapeSymbol.blank :: Lc) (marks ++ TapeSymbol.blank :: Rc))
with hT2
have hT2c : T2 g = cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc) := by rw [hT2]; simp
have hT2w : T2 w = ((moveDir HeadMove.left)^[marks.length]) (T w) := by
rw [hT2, Function.update_of_ne (fun h => hgw h.symm)]
exact hT1w
obtain ⟨h2a, h2b⟩ := guidedStep_move_iterate g w hgw HeadMove.right marks T2
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hT2c])
obtain ⟨hW2, hW2t⟩ := guidedWalk_spec g w hgw HeadMove.right none
marks.length T2
(guidedStep_move_marks g w hgw HeadMove.right marks T2
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) hnb (by rw [hT2c]))
(by rw [h2a]; rfl)
set T3 := ((guidedStep g w HeadMove.right none)^[marks.length]) T2 with hT3
have hT3c : T3 g = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) := h2a
obtain ⟨hR2, hR2t⟩ := rewindRun_spec g marks Lc Rc TapeSymbol.blank T3
hnb (by rw [hT3c])
refine ⟨_, 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' : ((digRoundTrip g w).step^[_])
((digRoundTrip g w).startCfg T) = _ := hfin
rw [hfin']
show (((rewindRun g).step^[_]) ((rewindRun g).startCfg T3)).tape = _
rw [hR2t]
funext j
by_cases hj : j = g
· subst hj
rw [Function.update_self, Function.update_of_ne hgw, hc]
· rw [Function.update_of_ne hj]
by_cases hj2 : j = w
· subst hj2
rw [Function.update_self, h2b, hT2w]
· rw [Function.update_of_ne hj2, hT3,
guidedStep_other g w HeadMove.right none marks.length T2 j hj hj2,
hT2, Function.update_of_ne hj, hT1,
guidedStep_other g w HeadMove.left none marks.length T j hj hj2]
set_option maxHeartbeats 4000000 in
/-- **The reservoir costs `18m + 31`.** -/
theorem counterSetup2_specB (gd cnt : Fin tapes) (hgc : gd ≠ cnt)
(marks Lg Rg : List TapeSymbol) (T : Fin tapes → Tape)
(hnb : ∀ x ∈ marks, x ≠ TapeSymbol.blank)
(hg : T gd = cellsTape (TapeSymbol.blank :: Lg)
(marks ++ TapeSymbol.blank :: Rg))
(hc : T cnt = cellsTape [] []) :
∃ cost : Nat,
cost ≤ 18 * marks.length + 31 ∧
HaltsExactly (counterSetup2 gd cnt)
((counterSetup2 gd cnt).startCfg T) cost true ∧
(((counterSetup2 gd cnt).step^[cost])
((counterSetup2 gd cnt).startCfg T)).tape =
Function.update T cnt
(cellsTape (List.replicate (marks.length + 2) TapeSymbol.blank)
[]) := by
classical
have g1 := moveUpTo_spec cnt 2 HeadMove.left (by omega) T
set T1 := Function.update T cnt
(((moveDir HeadMove.left)^[2]) (T cnt)) with hT1
have s1 : (((moveUpTo cnt 2 HeadMove.left).step^[2])
((moveUpTo cnt 2 HeadMove.left).startCfg T)).tape = T1 := by
rw [moveUpTo_tape cnt 2 HeadMove.left (by omega) T, hT1]
have hT1g : T1 gd = cellsTape (TapeSymbol.blank :: Lg)
(marks ++ TapeSymbol.blank :: Rg) := by
rw [hT1, Function.update_of_ne hgc]
exact hg
obtain ⟨c2, hb2, g2, s2⟩ := digRoundTrip_specB gd cnt hgc marks Lg Rg T1 hnb hT1g
set T2 := Function.update T1 cnt
(((moveDir HeadMove.right)^[marks.length])
(((moveDir HeadMove.left)^[marks.length]) (T1 cnt))) with hT2
have g3 := moveUpTo_spec cnt 2 HeadMove.right (by omega) T2
have s3 : (((moveUpTo cnt 2 HeadMove.right).step^[2])
((moveUpTo cnt 2 HeadMove.right).startCfg T2)).tape =
Function.update T2 cnt (((moveDir HeadMove.right)^[2]) (T2 cnt)) := by
rw [moveUpTo_tape cnt 2 HeadMove.right (by omega) T2]
have k2 := chainStepC g2 s2 g3
have k1 := chainStepC g1 s1 k2.1
refine ⟨_, by omega, k1.1, ?_⟩
have hfin := k1.2
rw [k2.2] at hfin
have hfin' : ((counterSetup2 gd cnt).step^[_])
((counterSetup2 gd cnt).startCfg T) = _ := hfin
rw [hfin']
show (((moveUpTo cnt 2 HeadMove.right).step^[2])
((moveUpTo cnt 2 HeadMove.right).startCfg T2)).tape = _
rw [s3]
funext j
by_cases hj : j = cnt
· subst hj
rw [Function.update_self, Function.update_self, hT2, Function.update_self,
hT1, Function.update_self, hc]
exact digRoundTrip_tapeK 2 marks.length
· rw [Function.update_of_ne hj, Function.update_of_ne hj, hT2,
Function.update_of_ne hj, hT1, Function.update_of_ne hj]
set_option maxHeartbeats 4000000 in
/-- **The guide and counter cost `31|x| + 52`.** -/
theorem guideSetup_specB (src gd cnt : Fin tapes)
(hsg : src ≠ gd) (hgc : gd ≠ cnt) (hsc : src ≠ cnt)
(x Ls Rs : List TapeSymbol) (T : Fin tapes → Tape)
(hnb : ∀ c ∈ x, c ≠ TapeSymbol.blank)
(hs : T src = cellsTape (TapeSymbol.blank :: Ls)
(x ++ TapeSymbol.blank :: Rs))
(hg : T gd = cellsTape [TapeSymbol.blank] [])
(hc : T cnt = cellsTape [] []) :
∃ cost : Nat,
cost ≤ 31 * x.length + 52 ∧
HaltsExactly (guideSetup src gd cnt)
((guideSetup src gd cnt).startCfg T) cost true ∧
(((guideSetup src gd cnt).step^[cost])
((guideSetup src gd cnt).startCfg T)).tape =
Function.update (Function.update T cnt
(cellsTape (List.replicate (x.length + 2) TapeSymbol.blank) []))
gd (cellsTape []
(List.replicate (x.length + 1) (TapeSymbol.bit true) ++
[TapeSymbol.blank])) := by
classical
obtain ⟨c1, hb1, g1, s1⟩ := markBack_specB src gd hsg x Ls [] Rs []
T hnb hs (by rw [hg])
set T1 := Function.update (Function.update T src
(cellsTape (TapeSymbol.blank :: Ls) (x ++ TapeSymbol.blank :: Rs))) gd
(cellsTape [TapeSymbol.blank]
(List.replicate x.length (TapeSymbol.bit true) ++
(List.drop x.length ([] : List TapeSymbol)).headD TapeSymbol.blank ::
(List.drop x.length ([] : List TapeSymbol)).tail)) with hT1
have hT1g : T1 gd = cellsTape (TapeSymbol.blank :: [])
(List.replicate x.length (TapeSymbol.bit true) ++
TapeSymbol.blank :: []) := by
rw [hT1, Function.update_self]
simp
have hT1c : T1 cnt = cellsTape [] [] := by
rw [hT1, Function.update_of_ne (Ne.symm hgc),
Function.update_of_ne (Ne.symm hsc)]
exact hc
have hmk : ∀ y ∈ List.replicate x.length (TapeSymbol.bit true),
y ≠ TapeSymbol.blank := by
intro y hy
rw [List.eq_of_mem_replicate hy]
simp
obtain ⟨c2, hb2, g2, s2⟩ := counterSetup2_specB gd cnt hgc
(List.replicate x.length (TapeSymbol.bit true)) [] [] T1 hmk hT1g hT1c
set T2 := Function.update T1 cnt
(cellsTape (List.replicate
((List.replicate x.length (TapeSymbol.bit true)).length + 2)
TapeSymbol.blank) []) with hT2
have hT2g : T2 gd = cellsTape (TapeSymbol.blank :: [])
(List.replicate x.length (TapeSymbol.bit true) ++
TapeSymbol.blank :: []) := by
rw [hT2, Function.update_of_ne hgc]
exact hT1g
obtain ⟨g3, s3⟩ := bumpCounter_spec gd x.length [] [] T2 hT2g
have k2 := chainStepC g2 s2 g3
have k1 := chainStepC g1 s1 k2.1
refine ⟨_, by simp at hb2; omega, k1.1, ?_⟩
have hfin := k1.2
rw [k2.2] at hfin
have hfin' : ((guideSetup src gd cnt).step^[_])
((guideSetup src gd cnt).startCfg T) = _ := hfin
rw [hfin']
show (((bumpCounter gd).step^[1 + 1 + 1])
((bumpCounter gd).startCfg T2)).tape = _
rw [s3]
funext j
by_cases hj : j = gd
· subst hj
rw [Function.update_self, Function.update_self]
· rw [Function.update_of_ne hj, Function.update_of_ne hj, hT2]
by_cases hj2 : j = cnt
· subst hj2
rw [Function.update_self, Function.update_self]
simp
· rw [Function.update_of_ne hj2, Function.update_of_ne hj2, hT1,
Function.update_of_ne hj]
by_cases hj3 : j = src
· subst hj3
rw [Function.update_self]
exact hs.symm
· rw [Function.update_of_ne hj3]
end SipserGacsLautemann