The skip, specified
Definitionsgl_skip_speccomplexity-theoryinfrastructuretheoretical-computer-scienceturing-machines
The skip, specified. Two guided passes over the clock advance the worker by twice the clock's length and leave the clock exactly as it was — the form a round consumes four times, once per working tape.
The worker's new position is stated as applied to its tape, which is the formulation that survives the worker running off the end of its written region; every other tape is untouched. The clock's restoration is what makes the four uses independent: each skip can assume the same clock shape as the last left it.
This completes the primitive published earlier with only its per-round lemmas. Every stage of the round now has a top-level statement: rewind, skip, restore, mark, and delegate.
Definition code
import Definitions.Def_sgl_offset_round
/-!
# The skip, specified
`skipAhead` was defined with its per-round lemmas; this is its top-level
statement. Two guided passes over the clock advance the worker by twice the
clock's length and leave the clock exactly as it was — the form a round
consumes four times.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
set_option maxHeartbeats 4000000 in
/-- **Advance the worker by twice the clock's marks, clock restored.** -/
theorem skipAhead_spec (clk w : Fin tapes) (hcw : clk ≠ w)
(marks Lc Rc : List TapeSymbol) (T : Fin tapes → Tape)
(hnb : ∀ x ∈ marks, x ≠ TapeSymbol.blank)
(hc : T clk = cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc)) :
∃ cost : Nat,
HaltsExactly (skipAhead clk w) ((skipAhead clk w).startCfg T) cost true ∧
(((skipAhead clk w).step^[cost])
((skipAhead clk w).startCfg T)).tape =
Function.update T w
(((moveDir HeadMove.right)^[marks.length + marks.length]) (T w)) := by
classical
set G := guidedStep clk w HeadMove.right none with hG
-- first pass
obtain ⟨h1a, h1b⟩ := guidedStep_skip_iterate clk w hcw marks T
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hc])
obtain ⟨hW1, hW1t⟩ := guidedWalk_spec clk w hcw HeadMove.right none
marks.length T
(guidedStep_skip_marks clk w hcw marks T (TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) hnb (by rw [hc]))
(by rw [h1a]; rfl)
set T1 := (G^[marks.length]) T with hT1
have hT1c : T1 clk = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) := h1a
have hT1w : T1 w = ((moveDir HeadMove.right)^[marks.length]) (T w) := h1b
-- first rewind
obtain ⟨hR1, hR1t⟩ := rewindRun_spec clk marks Lc Rc TapeSymbol.blank T1
hnb (by rw [hT1c])
set T2 := Function.update T1 clk
(cellsTape (TapeSymbol.blank :: Lc) (marks ++ TapeSymbol.blank :: Rc))
with hT2
have hT2c : T2 clk = cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc) := by rw [hT2]; simp
have hT2w : T2 w = ((moveDir HeadMove.right)^[marks.length]) (T w) := by
rw [hT2, Function.update_of_ne (fun h => hcw h.symm)]
exact hT1w
-- second pass
obtain ⟨h2a, h2b⟩ := guidedStep_skip_iterate clk w hcw marks T2
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hT2c])
obtain ⟨hW2, hW2t⟩ := guidedWalk_spec clk w hcw HeadMove.right none
marks.length T2
(guidedStep_skip_marks clk w hcw marks T2 (TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) hnb (by rw [hT2c]))
(by rw [h2a]; rfl)
set T3 := (G^[marks.length]) T2 with hT3
have hT3c : T3 clk = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) := h2a
-- second rewind
obtain ⟨hR2, hR2t⟩ := rewindRun_spec clk 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' : ((skipAhead clk w).step^[_])
((skipAhead clk w).startCfg T) = _ := hfin
rw [hfin']
show (((rewindRun clk).step^[_]) ((rewindRun clk).startCfg T3)).tape = _
rw [hR2t]
funext j
by_cases hj : j = clk
· subst hj
rw [Function.update_self, Function.update_of_ne hcw, hc]
· rw [Function.update_of_ne hj]
by_cases hj2 : j = w
· subst hj2
rw [Function.update_self, h2b, hT2w, ← Function.iterate_add_apply]
· rw [Function.update_of_ne hj2, hT3,
guidedStep_other clk w HeadMove.right none marks.length T2 j hj hj2,
hT2, Function.update_of_ne hj, hT1,
guidedStep_other clk w HeadMove.right none marks.length T j hj hj2]
end SipserGacsLautemann
Source
Top-level statement for skipAhead; builds on Def_sgl_offset_round.