sgl_walk_costs
DefinitionDefinition code
import Definitions.Def_sgl_offset_answer
/-!
# What the prologue costs
Each setup stage's specification hides its running time behind an existential,
which is fine for correctness and useless for a time bound — and a halting cost
cannot be recovered after the fact, since `HaltsExactly` pins it and the
statement never says to what. So the stages are restated with their costs
named.
The proofs are the originals unchanged. Every primitive underneath already
reports an exact cost — a guided walk takes `5m + 4`, a rewind `4m + 5`, an
origin marker three steps — so the chain's total is a concrete expression and
the bound is arithmetic.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
set_option maxHeartbeats 4000000 in
/-- **The normalising walk costs `9|x| + 10`.** -/
theorem normalizeInput_specB (s w : Fin tapes) (hsw : s ≠ w)
(x : List TapeSymbol) (T : Fin tapes → Tape)
(hnb : ∀ c ∈ x, c ≠ TapeSymbol.blank)
(hs : T s = cellsTape [TapeSymbol.blank] x) :
∃ cost : Nat,
cost ≤ 9 * x.length + 10 ∧
HaltsExactly (normalizeInput s w)
((normalizeInput s w).startCfg T) cost true ∧
(((normalizeInput s w).step^[cost])
((normalizeInput s w).startCfg T)).tape =
Function.update T s
(cellsTape [TapeSymbol.blank] (x ++ [TapeSymbol.blank])) := by
classical
obtain ⟨hia, hib⟩ := guidedStep_move_iterate s w hsw HeadMove.stay x T
[TapeSymbol.blank] [] (by rw [hs]; simp)
obtain ⟨hW, hWt⟩ := guidedWalk_spec s w hsw HeadMove.stay none x.length T
(guidedStep_move_marks s w hsw HeadMove.stay x T [TapeSymbol.blank] []
hnb (by rw [hs]; simp))
(by rw [hia]; rfl)
set T1 := ((guidedStep s w HeadMove.stay none)^[x.length]) T with hT1
have hT1s : T1 s = cellsTape (x.reverse ++ TapeSymbol.blank :: [])
(TapeSymbol.blank :: []) := by
rw [hia]
rfl
obtain ⟨hR, hRt⟩ := rewindRun_spec s x [] [] TapeSymbol.blank T1 hnb hT1s
have hch := chainStepC hW hWt hR
refine ⟨_, by omega, hch.1, ?_⟩
have hfin : ((normalizeInput s w).step^[_])
((normalizeInput s w).startCfg T) = _ := hch.2
rw [hfin]
show (((rewindRun s).step^[_]) ((rewindRun s).startCfg T1)).tape = _
rw [hRt]
funext j
by_cases hj : j = s
· subst hj
rw [Function.update_self, Function.update_self]
· rw [Function.update_of_ne hj, Function.update_of_ne hj]
by_cases hj2 : j = w
· rw [hj2]
exact hib.trans (moveDir_stay_iterate x.length (T w))
· rw [hT1, guidedStep_other s w HeadMove.stay none x.length T j hj hj2]
set_option maxHeartbeats 4000000 in
/-- **One tally costs `9|x| + 10`.** -/
theorem tallyOnto_specB (s w : Fin tapes) (hsw : s ≠ w)
(x Ls Rs Lw Rw : List TapeSymbol) (T : Fin tapes → Tape)
(hnb : ∀ c ∈ x, c ≠ TapeSymbol.blank)
(hs : T s = cellsTape (TapeSymbol.blank :: Ls)
(x ++ TapeSymbol.blank :: Rs))
(hw : T w = cellsTape Lw Rw) :
∃ cost : Nat,
cost ≤ 9 * x.length + 10 ∧
HaltsExactly (tallyOnto s w) ((tallyOnto s w).startCfg T) cost true ∧
(((tallyOnto s w).step^[cost]) ((tallyOnto s w).startCfg T)).tape =
Function.update T w
(cellsTape (List.replicate x.length (TapeSymbol.bit true) ++ Lw)
(Rw.drop x.length)) := by
classical
obtain ⟨hia, hib⟩ := guidedStep_write_iterate s w hsw x T
(TapeSymbol.blank :: Ls) (TapeSymbol.blank :: Rs) Lw Rw (by rw [hs]) hw
obtain ⟨hW, hWt⟩ := guidedWalk_spec s w hsw HeadMove.right
(some (TapeSymbol.bit true)) x.length T
(guidedStep_write_marks s w hsw x T (TapeSymbol.blank :: Ls)
(TapeSymbol.blank :: Rs) Lw Rw hnb (by rw [hs]) hw)
(by rw [hia]; rfl)
set T1 := ((guidedStep s w HeadMove.right
(some (TapeSymbol.bit true)))^[x.length]) T with hT1
have hT1s : T1 s = cellsTape (x.reverse ++ TapeSymbol.blank :: Ls)
(TapeSymbol.blank :: Rs) := hia
obtain ⟨hR, hRt⟩ := rewindRun_spec s x Ls Rs TapeSymbol.blank T1 hnb
(by rw [hT1s])
have hch := chainStepC hW hWt hR
refine ⟨_, by omega, hch.1, ?_⟩
have hfin : ((tallyOnto s w).step^[_])
((tallyOnto s w).startCfg T) = _ := hch.2
rw [hfin]
show (((rewindRun s).step^[_]) ((rewindRun s).startCfg T1)).tape = _
rw [hRt]
funext j
by_cases hj : j = s
· subst hj
rw [Function.update_self, Function.update_of_ne hsw, hs]
· rw [Function.update_of_ne hj]
by_cases hj2 : j = w
· subst hj2
rw [Function.update_self]
exact hib
· rw [Function.update_of_ne hj2, hT1,
guidedStep_other s w HeadMove.right (some (TapeSymbol.bit true))
x.length T j hj hj2]
set_option maxHeartbeats 4000000 in
/-- **Readying one input costs `9|x| + 14`.** -/
theorem inputPrep_specB (s w : Fin tapes) (hsw : s ≠ w)
(x : List TapeSymbol) (T : Fin tapes → Tape)
(hnb : ∀ c ∈ x, c ≠ TapeSymbol.blank)
(hs : T s = cellsTape [] x) :
∃ cost : Nat,
cost ≤ 9 * x.length + 14 ∧
HaltsExactly (inputPrep s w) ((inputPrep s w).startCfg T) cost true ∧
(((inputPrep s w).step^[cost]) ((inputPrep s w).startCfg T)).tape =
Function.update T s
(cellsTape [TapeSymbol.blank] (x ++ [TapeSymbol.blank])) := by
classical
obtain ⟨g1, s1⟩ := prepTape_spec s T x hs
set T1 := Function.update T s (cellsTape [TapeSymbol.blank] x) with hT1
have hT1s : T1 s = cellsTape [TapeSymbol.blank] x := by
rw [hT1, Function.update_self]
obtain ⟨c2, hb2, g2, s2⟩ := normalizeInput_specB s w hsw x T1 hnb hT1s
have hch := chainStepC g1 s1 g2
refine ⟨_, by omega, hch.1, ?_⟩
have hfin : ((inputPrep s w).step^[_])
((inputPrep s w).startCfg T) = _ := hch.2
rw [hfin]
show (((normalizeInput s w).step^[c2])
((normalizeInput s w).startCfg T1)).tape = _
rw [s2, hT1, Function.update_idem]
end SipserGacsLautemann