sgl_dig_left
DefinitionDefinition code
import Definitions.Def_sgl_offset_cost
/-!
# Digging a blank reservoir
The counter's left context must hold one blank per round: each bump spends one,
and a counter that runs out cannot be bumped again. A freshly provisioned
scratch tape has *no* left context at all — the zipper is empty on that side —
so the reservoir has to be excavated before the loop starts.
Excavating it is a round trip. Walking left off the end of a zipper
materialises a blank on the right, and walking back right pushes those blanks
into the left context, so `m` steps out and `m` steps back leaves the head where
it started with `m` blanks behind it. Neither pass writes anything.
`moveUpTo` cannot do this — it is capped at twelve steps — so the walk is
guided by a tape that already carries `m` marks, exactly as `skipAhead` is.
`digRoundTrip` is `skipAhead` with its first pass reversed, and the guide's own
lemmas are direction-generic once the worker's direction is freed from the
guide's.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## The guide's lemmas, with the worker's direction free -/
/-- One round of a guided walk, in `cellsTape` form, for any worker
direction. -/
theorem guidedStep_move (g w : Fin tapes) (hgw : g ≠ w) (dir : HeadMove)
(T : Fin tapes → Tape) (a : TapeSymbol) (Lg Rg : List TapeSymbol)
(hg : T g = cellsTape Lg (a :: Rg)) :
(guidedStep g w dir none T) g = cellsTape (a :: Lg) Rg ∧
(guidedStep g w dir none T) w = moveDir dir (T w) := by
constructor
· show (if g = g then moveDir HeadMove.right (T g) else _) = _
rw [if_pos rfl, hg, cellsTape_moveRight]
· show (if w = g then _ else if w = w then moveDir dir (T w) else _) = _
rw [if_neg (fun h => hgw h.symm), if_pos rfl]
theorem guidedStep_move_iterate (g w : Fin tapes) (hgw : g ≠ w)
(dir : HeadMove) :
∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
(Lg Rg : List TapeSymbol),
T g = cellsTape Lg (marks ++ Rg) →
(((guidedStep g w dir none)^[marks.length]) T) g =
cellsTape (marks.reverse ++ Lg) Rg ∧
(((guidedStep g w dir none)^[marks.length]) T) w =
((moveDir dir)^[marks.length]) (T w) := by
intro marks
induction marks with
| nil => intro T Lg Rg hg; simpa using hg
| cons a marks ih =>
intro T Lg Rg hg
obtain ⟨h1, h2⟩ := guidedStep_move g w hgw dir T a Lg (marks ++ Rg)
(by rw [hg]; rfl)
obtain ⟨i1, i2⟩ := ih (guidedStep g w dir none T) (a :: Lg) Rg (by rw [h1])
rw [List.length_cons, Function.iterate_succ_apply]
refine ⟨by rw [i1]; congr 1; simp, ?_⟩
rw [i2, h2, Function.iterate_succ_apply]
theorem guidedStep_move_marks (g w : Fin tapes) (hgw : g ≠ w)
(dir : HeadMove) :
∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
(Lg Rg : List TapeSymbol),
(∀ c ∈ marks, c ≠ TapeSymbol.blank) →
T g = cellsTape Lg (marks ++ Rg) →
∀ r, r < marks.length →
(((((guidedStep g w dir none)^[r]) T) g).head ≠ TapeSymbol.blank) := by
intro marks
induction marks with
| nil => intro _ _ _ _ _ r hr; simp at hr
| cons a marks ih =>
intro T Lg Rg hnb hg r hr
cases r with
| zero =>
rw [Function.iterate_zero_apply, hg]
exact hnb a (by simp)
| succ r =>
obtain ⟨h1, _⟩ := guidedStep_move g w hgw dir T a Lg (marks ++ Rg)
(by rw [hg]; rfl)
rw [Function.iterate_succ_apply]
exact ih (guidedStep g w dir none T) (a :: Lg) Rg
(fun c hc => hnb c (by simp [hc])) (by rw [h1])
r (by simpa using hr)
/-! ## The machine -/
/-- Walk the worker `m` cells left and back, guided by `m` marks. -/
def digRoundTrip (g w : Fin tapes) :=
(guidedWalk g w HeadMove.left none).andThen fun _ =>
(rewindRun g).andThen fun _ =>
(guidedWalk g w HeadMove.right none).andThen fun _ =>
rewindRun g
set_option maxHeartbeats 4000000 in
/-- **The reservoir.** Guided by `m` marks, the worker walks `m` cells left
and `m` cells back, and the guide is restored exactly. -/
theorem digRoundTrip_spec (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,
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 ⟨_, (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]
/-! ## What the round trip does to a blank tape -/
/-- Walking left off the end materialises blanks on the right. -/
theorem moveLeft_blanks (j : Nat) : ∀ m : Nat,
((moveDir HeadMove.left)^[m])
(⟨[], TapeSymbol.blank, List.replicate j TapeSymbol.blank⟩ : Tape) =
⟨[], TapeSymbol.blank, List.replicate (m + j) TapeSymbol.blank⟩ := by
intro m
induction m with
| zero => simp
| succ m ih =>
rw [Function.iterate_succ_apply', ih]
show (⟨[], TapeSymbol.blank,
TapeSymbol.blank :: List.replicate (m + j) TapeSymbol.blank⟩ : Tape) = _
rw [← List.replicate_succ]
congr 2
omega
/-- Walking back right pushes them into the left context. -/
theorem moveRight_blanks (j : Nat) : ∀ (m k : Nat),
((moveDir HeadMove.right)^[m])
(⟨List.replicate k TapeSymbol.blank, TapeSymbol.blank,
List.replicate (m + j) TapeSymbol.blank⟩ : Tape) =
⟨List.replicate (k + m) TapeSymbol.blank, TapeSymbol.blank,
List.replicate j TapeSymbol.blank⟩ := by
intro m
induction m with
| zero => intro k; simp
| succ m ih =>
intro k
rw [Function.iterate_succ_apply]
have hstep : moveDir HeadMove.right
(⟨List.replicate k TapeSymbol.blank, TapeSymbol.blank,
List.replicate (m + 1 + j) TapeSymbol.blank⟩ : Tape) =
⟨List.replicate (k + 1) TapeSymbol.blank, TapeSymbol.blank,
List.replicate (m + j) TapeSymbol.blank⟩ := by
rw [show m + 1 + j = (m + j) + 1 by omega, List.replicate_succ,
List.replicate_succ]
rfl
rw [hstep, ih (k + 1)]
congr 2
omega
/-- **The excavation, as a tape equation.** One step left, a round trip of
`m`, and one step right leave the head where it started with `m + 1` blanks
behind it. -/
theorem digRoundTrip_tape (m : Nat) :
moveDir HeadMove.right
(((moveDir HeadMove.right)^[m])
(((moveDir HeadMove.left)^[m])
(moveDir HeadMove.left (cellsTape [] ([] : List TapeSymbol))))) =
cellsTape (List.replicate (m + 1) TapeSymbol.blank) [] := by
have h0 : moveDir HeadMove.left (cellsTape [] ([] : List TapeSymbol)) =
⟨[], TapeSymbol.blank, List.replicate 1 TapeSymbol.blank⟩ := rfl
rw [h0, moveLeft_blanks 1 m]
have h1 : ((moveDir HeadMove.right)^[m])
(⟨[], TapeSymbol.blank, List.replicate (m + 1) TapeSymbol.blank⟩ :
Tape) =
⟨List.replicate m TapeSymbol.blank, TapeSymbol.blank,
[TapeSymbol.blank]⟩ := by
have h := moveRight_blanks 1 m 0
simpa using h
rw [h1]
show (⟨TapeSymbol.blank :: List.replicate m TapeSymbol.blank,
TapeSymbol.blank, []⟩ : Tape) = _
rw [← List.replicate_succ]
rfl
end SipserGacsLautemann