sgl_guide_setup
DefinitionDefinition code
import Definitions.Def_sgl_counter_setup
/-!
# Setting the guide up, and widening the reservoir
The guide is a consumable tally of the offsets: one mark per cell of the third
input, plus one, so the loop runs `|xs 2| + 1` rounds and tries every offset
from `0` to `|xs 2|`. `markBack` writes the tally and `bumpCounter` adds the
extra mark.
The order of the prologue's stages is forced by their shapes. `markBack`
leaves its target with a blank explicitly to the left — which is what the dig
needs — and `bumpCounter` consumes that blank, which is what the loop's own
invariant wants. So the counter must be excavated *between* the two, while the
guide still carries only `|xs 2|` marks. The reservoir must nonetheless hold
`|xs 2| + 2` blanks, so the dig takes two extra steps in each direction rather
than one.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- The excavation with `k` extra steps on each side. -/
theorem digRoundTrip_tapeK (k m : Nat) :
((moveDir HeadMove.right)^[k])
(((moveDir HeadMove.right)^[m])
(((moveDir HeadMove.left)^[m])
(((moveDir HeadMove.left)^[k])
(cellsTape [] ([] : List TapeSymbol))))) =
cellsTape (List.replicate (m + k) TapeSymbol.blank) [] := by
have h0 : ((moveDir HeadMove.left)^[k])
(cellsTape [] ([] : List TapeSymbol)) =
⟨[], TapeSymbol.blank, List.replicate k TapeSymbol.blank⟩ := by
have h := moveLeft_blanks 0 k
simpa using h
rw [h0, moveLeft_blanks k m]
have h1 : ((moveDir HeadMove.right)^[m])
(⟨[], TapeSymbol.blank, List.replicate (m + k) TapeSymbol.blank⟩ :
Tape) =
⟨List.replicate m TapeSymbol.blank, TapeSymbol.blank,
List.replicate k TapeSymbol.blank⟩ := by
have h := moveRight_blanks k m 0
simpa using h
rw [h1]
have h2 : ((moveDir HeadMove.right)^[k])
(⟨List.replicate m TapeSymbol.blank, TapeSymbol.blank,
List.replicate k TapeSymbol.blank⟩ : Tape) =
⟨List.replicate (m + k) TapeSymbol.blank, TapeSymbol.blank, []⟩ := by
have h := moveRight_blanks 0 k m
simpa using h
rw [h2]
rfl
/-- Excavate a reservoir two cells wider than the guide's tally. -/
def counterSetup2 (gd cnt : Fin tapes) :=
(moveUpTo cnt 2 HeadMove.left).andThen fun _ =>
(digRoundTrip gd cnt).andThen fun _ =>
moveUpTo cnt 2 HeadMove.right
set_option maxHeartbeats 4000000 in
/-- **The reservoir, two wider.** -/
theorem counterSetup2_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 (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, 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 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 ⟨_, 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]
/-! ## The guide and the counter, together -/
/-- Tally the third input onto the guide, excavate the counter beside it, then
add the guide's last mark. -/
def guideSetup (src gd cnt : Fin tapes) :=
(markBack src gd).andThen fun _ =>
(counterSetup2 gd cnt).andThen fun _ =>
bumpCounter gd
set_option maxHeartbeats 4000000 in
/-- **Guide and counter, ready for round zero.** The guide carries one mark
per cell of the input plus one, head on the first; the counter is empty with a
reservoir one longer than the guide; the input is restored. -/
theorem guideSetup_spec (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,
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, g1, s1⟩ := markBack_spec 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, g2, s2⟩ := counterSetup2_spec 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 ⟨_, 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