sgl_counter_setup
DefinitionDefinition code
import Definitions.Def_sgl_dig_left
/-!
# Setting the counter up
Three stages: step left off the tape's origin, walk out and back guided by the
guide's marks, step right again. The net effect on a virgin scratch tape is to
leave the head exactly where it started with one blank per round behind it —
the reservoir every bump spends from.
Nothing is written at any point. The blanks are not written blanks; they are
the cells the zipper materialises when the head walks past its own end, moved
into the left context by walking back. That is the only way to obtain them,
since writing a blank onto a cell that is already blank changes nothing about
the representation.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Excavate the counter's reservoir, using the guide as the ruler. -/
def counterSetup (gd cnt : Fin tapes) :=
(moveUpTo cnt 1 HeadMove.left).andThen fun _ =>
(digRoundTrip gd cnt).andThen fun _ =>
moveUpTo cnt 1 HeadMove.right
set_option maxHeartbeats 4000000 in
/-- **The reservoir, in place.** From a virgin counter tape and a guide
carrying `marks`, the counter ends with `|marks| + 1` blanks to the left of its
head and the guide is untouched. -/
theorem counterSetup_spec (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,
HaltsExactly (counterSetup gd cnt)
((counterSetup gd cnt).startCfg T) cost true ∧
(((counterSetup gd cnt).step^[cost])
((counterSetup gd cnt).startCfg T)).tape =
Function.update T cnt
(cellsTape (List.replicate (marks.length + 1) TapeSymbol.blank) []) := by
classical
have g1 := moveUpTo_spec cnt 1 HeadMove.left (by omega) T
set T1 := Function.update T cnt (moveDir HeadMove.left (T cnt)) with hT1
have s1 : (((moveUpTo cnt 1 HeadMove.left).step^[1])
((moveUpTo cnt 1 HeadMove.left).startCfg T)).tape = T1 := by
rw [moveUpTo_tape cnt 1 HeadMove.left (by omega) T, hT1,
Function.iterate_one]
have hT1g : T1 gd = cellsTape (TapeSymbol.blank :: Lg)
(marks ++ TapeSymbol.blank :: Rg) := by
rw [hT1, Function.update_of_ne hgc]
exact hg
obtain ⟨c2, g2, s2⟩ := digRoundTrip_spec 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 1 HeadMove.right (by omega) T2
have s3 : (((moveUpTo cnt 1 HeadMove.right).step^[1])
((moveUpTo cnt 1 HeadMove.right).startCfg T2)).tape =
Function.update T2 cnt (moveDir HeadMove.right (T2 cnt)) := by
rw [moveUpTo_tape cnt 1 HeadMove.right (by omega) T2, Function.iterate_one]
have k2 := chainStepC g2 s2 g3
have k1 := chainStepC g1 s1 k2.1
refine ⟨_, k1.1, ?_⟩
have hfin := k1.2
rw [k2.2] at hfin
have hfin' : ((counterSetup gd cnt).step^[_])
((counterSetup gd cnt).startCfg T) = _ := hfin
rw [hfin']
show (((moveUpTo cnt 1 HeadMove.right).step^[1])
((moveUpTo cnt 1 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_tape 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]
end SipserGacsLautemann