sgl_skip_margin
DefinitionDefinition code
import Definitions.Def_sgl_tape_locality
/-!
# How much blank the skip leaves behind
`skip_exhausts` says a long enough rightward walk lands on clean tape. It says
nothing about what is behind the head, and behind the head is where the
previous round's leavings are. For a delegate to be unable to reach them, the
walk has to overshoot by more than the delegate's own time bound, and the
statement has to record that it did.
The count is exact: a walk of `m` over a written region of length `q` puts
`m - q - 1` blanks between the head and the leavings, because every cell past
the region is one the head has never visited. Asking for `q + p + 2 ≤ m` is
asking for `p` of them.
-/
namespace SipserGacsLautemann
/-- **The skip, with its margin.** A walk that overshoots the written region
by `p + 2` leaves at least `p` blanks behind the head before anything else. -/
theorem skipRight_exhausts_blanks :
∀ (R L : List TapeSymbol) (h : TapeSymbol) (m p : Nat),
R.length + p + 2 ≤ m →
∃ L' : List TapeSymbol,
((moveDir HeadMove.right)^[m]) (⟨L, h, R⟩ : Tape) =
cellsTape (TapeSymbol.blank ::
(List.replicate p TapeSymbol.blank ++ L')) [] := by
intro R
induction R with
| nil =>
intro L h m p hm
obtain ⟨m', rfl⟩ : ∃ m', m = m' + 2 := ⟨m - 2, by simp at hm; omega⟩
refine ⟨List.replicate (m' - p) TapeSymbol.blank ++ h :: L, ?_⟩
rw [moveRight_past_nil L h m']
congr 2
rw [← List.append_assoc, ← List.replicate_add]
congr 2
simp at hm
omega
| cons s R ih =>
intro L h m p hm
obtain ⟨m', rfl⟩ : ∃ m', m = m' + 1 := ⟨m - 1, by simp at hm; omega⟩
rw [Function.iterate_succ_apply]
have hstep : moveDir HeadMove.right (⟨L, h, s :: R⟩ : Tape) =
⟨h :: L, s, R⟩ := rfl
rw [hstep]
exact ih (h :: L) s m' p (by simp at hm; omega)
/-- The same, for a tape given abstractly. -/
theorem skip_exhausts_blanks (tp : Tape) (m p : Nat)
(hm : tp.right.length + p + 2 ≤ m) :
∃ L' : List TapeSymbol,
((moveDir HeadMove.right)^[m]) tp =
cellsTape (TapeSymbol.blank ::
(List.replicate p TapeSymbol.blank ++ L')) [] := by
cases tp with
| mk L h R => exact skipRight_exhausts_blanks R L h m p hm
/-- **The re-entry condition, with a margin.** -/
theorem delegate_leaves_skippable_blanks {tapes states : Nat}
(M : Machine tapes states) (cfg : Configuration tapes states)
(j : Fin tapes) (Tm q m p : Nat)
(hq : (cfg.tape j).right.length ≤ q)
(hm : q + Tm + p + 2 ≤ m) :
∃ L' : List TapeSymbol,
((moveDir HeadMove.right)^[m]) (((M.step^[Tm]) cfg).tape j) =
cellsTape (TapeSymbol.blank ::
(List.replicate p TapeSymbol.blank ++ L')) [] := by
refine skip_exhausts_blanks _ m p ?_
have := right_length_run M cfg j Tm
omega
/-! ## What a margin buys -/
/-- A tape whose left context begins with `t` blanks agrees, out to radius `t`,
with the same tape read from an empty left context. -/
theorem agree_of_blank_margin (p : Nat) (L' R : List TapeSymbol)
(t : Nat) (ht : t ≤ p + 1) :
TapeAgree t
(cellsTape (TapeSymbol.blank ::
(List.replicate p TapeSymbol.blank ++ L')) R)
(cellsTape [] R) := by
refine ⟨rfl, ?_, fun i _ => rfl⟩
intro i hi
show (TapeSymbol.blank ::
(List.replicate p TapeSymbol.blank ++ L')).getD i TapeSymbol.blank =
([] : List TapeSymbol).getD i TapeSymbol.blank
rw [List.getD_nil]
cases i with
| zero => rfl
| succ i =>
show (List.replicate p TapeSymbol.blank ++ L').getD i TapeSymbol.blank
= TapeSymbol.blank
rw [List.getD_eq_getElem?_getD, List.getElem?_append_left (by rw [List.length_replicate]; omega)]
simp
end SipserGacsLautemann