sgl_clock_setup
DefinitionDefinition code
import Definitions.Def_sgl_guide_setup
/-!
# Setting the clock up
The clock must start long enough that its reach `2A` already covers the longest
input and the round count — after that the loop's own arithmetic keeps it ahead
forever. `Σ|xs| + 2` marks suffice, and they are written by tallying each input
in turn onto the same tape.
`markBack` cannot do the tallying, because it rewinds its *target* as well as
its source, and a rewind walks back over every mark it finds — so a second
tally would return to the first run's start rather than its own. Splitting the
rewinds apart fixes it: `tallyOnto` rewinds only the source, leaving the clock's
head exactly where the next run should begin. Three tallies then concatenate
by themselves, since consecutive runs of the same symbol are one run.
The two extra marks are written first rather than last, because the clock's
left context is unconstrained but its head must end past every mark.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Write a mark and advance. -/
def writeMark (i : Fin tapes) :=
TypedMachine.act (fun symbols j =>
if j = i then (TapeSymbol.bit true, HeadMove.right)
else (symbols j, HeadMove.stay))
theorem writeMark_spec (i : Fin tapes) (L R : List TapeSymbol)
(T : Fin tapes → Tape) (hT : T i = cellsTape L R) :
HaltsExactly (writeMark i) ((writeMark i).startCfg T) 1 true ∧
(((writeMark i).step^[1]) ((writeMark i).startCfg T)).tape =
Function.update T i (cellsTape (TapeSymbol.bit true :: L) R.tail) := by
classical
refine ⟨TypedMachine.act_spec
(fun symbols : Fin tapes → TapeSymbol => fun j =>
if j = i then (TapeSymbol.bit true, HeadMove.right)
else (symbols j, HeadMove.stay)) T, ?_⟩
rw [Function.iterate_one]
funext j
by_cases hj : j = i
· rw [hj]
have hcell : Tape.move (Tape.write (T i) (TapeSymbol.bit true))
HeadMove.right = cellsTape (TapeSymbol.bit true :: L) R.tail := by
rw [hT, write_cellsTape]
exact cellsTape_moveRight L (TapeSymbol.bit true) R.tail
simp [writeMark, TypedMachine.step, TypedMachine.act,
TypedMachine.startCfg, hcell]
· simp [writeMark, TypedMachine.step, TypedMachine.act,
TypedMachine.startCfg, hj, Tape.write_head_self, Tape.move]
/-- Tally one input onto a target, rewinding only the input. -/
def tallyOnto (s w : Fin tapes) :=
(guidedWalk s w HeadMove.right (some (TapeSymbol.bit true))).andThen fun _ =>
rewindRun s
set_option maxHeartbeats 4000000 in
/-- **One tally.** The target gains one mark per cell of the input and its head
sits past them; the input is restored. -/
theorem tallyOnto_spec (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,
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 ⟨_, 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]
/-! ## The clock, assembled -/
/-- Two marks, then one tally per input. -/
def clockSetup (s0 s1 s2 clk : Fin tapes) :=
(writeMark clk).andThen fun _ =>
(writeMark clk).andThen fun _ =>
(tallyOnto s0 clk).andThen fun _ =>
(tallyOnto s1 clk).andThen fun _ =>
tallyOnto s2 clk
set_option maxHeartbeats 4000000 in
/-- **The clock, long enough.** From a virgin clock tape the machine leaves
`|x0| + |x1| + |x2| + 2` marks with the head past all of them, every input
restored. -/
theorem clockSetup_spec (s0 s1 s2 clk : Fin tapes)
(h0 : s0 ≠ clk) (h1 : s1 ≠ clk) (h2 : s2 ≠ clk)
(x0 x1 x2 L0 L1 L2 R0 R1 R2 : List TapeSymbol) (T : Fin tapes → Tape)
(hn0 : ∀ c ∈ x0, c ≠ TapeSymbol.blank)
(hn1 : ∀ c ∈ x1, c ≠ TapeSymbol.blank)
(hn2 : ∀ c ∈ x2, c ≠ TapeSymbol.blank)
(hs0 : T s0 = cellsTape (TapeSymbol.blank :: L0)
(x0 ++ TapeSymbol.blank :: R0))
(hs1 : T s1 = cellsTape (TapeSymbol.blank :: L1)
(x1 ++ TapeSymbol.blank :: R1))
(hs2 : T s2 = cellsTape (TapeSymbol.blank :: L2)
(x2 ++ TapeSymbol.blank :: R2))
(hclk : T clk = cellsTape [TapeSymbol.blank] []) :
∃ cost : Nat,
HaltsExactly (clockSetup s0 s1 s2 clk)
((clockSetup s0 s1 s2 clk).startCfg T) cost true ∧
(((clockSetup s0 s1 s2 clk).step^[cost])
((clockSetup s0 s1 s2 clk).startCfg T)).tape =
Function.update T clk
(cellsTape (List.replicate
(x2.length + (x1.length + (x0.length + 2))) (TapeSymbol.bit true)
++ [TapeSymbol.blank]) []) := by
classical
obtain ⟨gA, sA⟩ := writeMark_spec clk [TapeSymbol.blank] [] T hclk
set TA := Function.update T clk
(cellsTape (TapeSymbol.bit true :: [TapeSymbol.blank])
([] : List TapeSymbol).tail) with hTA
have hTAclk : TA clk = cellsTape
(List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] := by
rw [hTA, Function.update_self]
simp
obtain ⟨gB, sB⟩ := writeMark_spec clk
(List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] TA hTAclk
set TB := Function.update TA clk
(cellsTape (TapeSymbol.bit true ::
(List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]))
([] : List TapeSymbol).tail) with hTB
have hTBclk : TB clk = cellsTape
(List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] := by
rw [hTB, Function.update_self]
simp [List.replicate_succ]
have hTBs : ∀ (s : Fin tapes), s ≠ clk → TB s = T s := by
intro s hs
rw [hTB, Function.update_of_ne hs, hTA, Function.update_of_ne hs]
obtain ⟨c1, g1, t1⟩ := tallyOnto_spec s0 clk h0 x0 L0 R0
(List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] TB hn0
(by rw [hTBs s0 h0]; exact hs0) hTBclk
set T1 := Function.update TB clk
(cellsTape (List.replicate x0.length (TapeSymbol.bit true) ++
(List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]))
(([] : List TapeSymbol).drop x0.length)) with hT1
have hT1clk : T1 clk = cellsTape
(List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) [] := by
rw [hT1, Function.update_self, ← List.append_assoc, ← List.replicate_add]
simp
have hT1s : ∀ (s : Fin tapes), s ≠ clk → T1 s = T s := by
intro s hs
rw [hT1, Function.update_of_ne hs]
exact hTBs s hs
obtain ⟨c2, g2, t2⟩ := tallyOnto_spec s1 clk h1 x1 L1 R1
(List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) [] T1 hn1
(by rw [hT1s s1 h1]; exact hs1) hT1clk
set T2 := Function.update T1 clk
(cellsTape (List.replicate x1.length (TapeSymbol.bit true) ++
(List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
[TapeSymbol.blank]))
(([] : List TapeSymbol).drop x1.length)) with hT2
have hT2clk : T2 clk = cellsTape
(List.replicate (x1.length + (x0.length + 2)) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) [] := by
rw [hT2, Function.update_self, ← List.append_assoc, ← List.replicate_add]
simp
have hT2s : ∀ (s : Fin tapes), s ≠ clk → T2 s = T s := by
intro s hs
rw [hT2, Function.update_of_ne hs]
exact hT1s s hs
obtain ⟨c3, g3, t3⟩ := tallyOnto_spec s2 clk h2 x2 L2 R2
(List.replicate (x1.length + (x0.length + 2)) (TapeSymbol.bit true) ++
[TapeSymbol.blank]) [] T2 hn2
(by rw [hT2s s2 h2]; exact hs2) hT2clk
have k3 := chainStepC g2 t2 g3
have k2 := chainStepC g1 t1 k3.1
have k1 := chainStepC gB sB k2.1
have k0 := chainStepC gA sA k1.1
refine ⟨_, k0.1, ?_⟩
have hfin := k0.2
rw [k1.2, k2.2, k3.2] at hfin
have hfin' : ((clockSetup s0 s1 s2 clk).step^[_])
((clockSetup s0 s1 s2 clk).startCfg T) = _ := hfin
rw [hfin']
show (((tallyOnto s2 clk).step^[c3])
((tallyOnto s2 clk).startCfg T2)).tape = _
rw [t3]
funext j
by_cases hj : j = clk
· subst hj
rw [Function.update_self, Function.update_self, ← List.append_assoc,
← List.replicate_add]
simp
· rw [Function.update_of_ne hj, Function.update_of_ne hj]
exact hT2s j hj
end SipserGacsLautemann