sgl_input_prep
DefinitionDefinition code
import Definitions.Def_sgl_clock_setup
/-!
# Making an input tape's shape explicit
A raw input tape is `Tape.ofBits`, whose right half is exactly the input's
cells and nothing more. Every lemma in the round instead wants
`cellsTape (blank :: Ls) (x ++ blank :: Rs)` — the terminating blank named in
the list. The two describe the *same* tape: positions past the written region
are blank either way, and a head that walks off the end materialises one. Only
the representation differs.
Walking to the end and back is what converts one into the other, and the input
can guide its own walk: a guided walk stops when its guide reads a blank, which
is exactly the cell past the input. Choosing `stay` for the worker's direction
makes the walk a pure measurement — nothing else on the tape space moves.
This is the same manoeuvre as the dilation's probe, which normalised a blank
context to explicit cells for the same reason.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Standing still is the identity, however long you do it. -/
theorem moveDir_stay_iterate (m : Nat) (tp : Tape) :
((moveDir HeadMove.stay)^[m]) tp = tp := by
induction m with
| zero => rfl
| succ m ih => rw [Function.iterate_succ_apply', ih]; rfl
/-- Walk an input to its end and back, touching nothing else. -/
def normalizeInput (s w : Fin tapes) :=
(guidedWalk s w HeadMove.stay none).andThen fun _ =>
rewindRun s
set_option maxHeartbeats 4000000 in
/-- **The input's shape, made explicit.** The head returns to the input's
first cell with the terminating blank now named in the representation. -/
theorem normalizeInput_spec (s w : Fin tapes) (hsw : s ≠ w)
(x : List TapeSymbol) (T : Fin tapes → Tape)
(hnb : ∀ c ∈ x, c ≠ TapeSymbol.blank)
(hs : T s = cellsTape [TapeSymbol.blank] x) :
∃ cost : Nat,
HaltsExactly (normalizeInput s w)
((normalizeInput s w).startCfg T) cost true ∧
(((normalizeInput s w).step^[cost])
((normalizeInput s w).startCfg T)).tape =
Function.update T s
(cellsTape [TapeSymbol.blank] (x ++ [TapeSymbol.blank])) := by
classical
obtain ⟨hia, hib⟩ := guidedStep_move_iterate s w hsw HeadMove.stay x T
[TapeSymbol.blank] [] (by rw [hs]; simp)
obtain ⟨hW, hWt⟩ := guidedWalk_spec s w hsw HeadMove.stay none x.length T
(guidedStep_move_marks s w hsw HeadMove.stay x T [TapeSymbol.blank] []
hnb (by rw [hs]; simp))
(by rw [hia]; rfl)
set T1 := ((guidedStep s w HeadMove.stay none)^[x.length]) T with hT1
have hT1s : T1 s = cellsTape (x.reverse ++ TapeSymbol.blank :: [])
(TapeSymbol.blank :: []) := by
rw [hia]
rfl
obtain ⟨hR, hRt⟩ := rewindRun_spec s x [] [] TapeSymbol.blank T1 hnb hT1s
have hch := chainStepC hW hWt hR
refine ⟨_, hch.1, ?_⟩
have hfin : ((normalizeInput s w).step^[_])
((normalizeInput 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_self]
· rw [Function.update_of_ne hj, Function.update_of_ne hj]
by_cases hj2 : j = w
· rw [hj2]
exact hib.trans (moveDir_stay_iterate x.length (T w))
· rw [hT1, guidedStep_other s w HeadMove.stay none x.length T j hj hj2]
end SipserGacsLautemann