sgl_clean_agree
DefinitionDefinition code
import Definitions.Def_sgl_traj_margin
/-!
# The round's tapes against the clean ones
A delegate's correctness is stated on `Tape.ofBits` tapes: empty left context,
right context exactly the input's cells. The round hands it something that
differs in two ways — a blank margin then debris on the left, and one extra
terminating blank on the right. Both are invisible.
The right-hand difference is invisible at every radius: appending a blank only
occupies a position that already read blank by default. The left-hand
difference is invisible out to the margin, which is what the margin is for.
Composing the two gives agreement at radius `B + 1`, and the delegate runs for
at most `B` steps.
-/
namespace SipserGacsLautemann
variable {n : Nat}
theorem TapeAgree.symm {t : Nat} {a b : Tape} (h : TapeAgree t a b) :
TapeAgree t b a :=
⟨h.head.symm, fun i hi => (h.left i hi).symm,
fun i hi => (h.right i hi).symm⟩
theorem TapeAgree.trans {t : Nat} {a b c : Tape} (h₁ : TapeAgree t a b)
(h₂ : TapeAgree t b c) : TapeAgree t a c :=
⟨h₁.head.trans h₂.head, fun i hi => (h₁.left i hi).trans (h₂.left i hi),
fun i hi => (h₁.right i hi).trans (h₂.right i hi)⟩
theorem getD_append_blank (l : List TapeSymbol) (i : Nat) :
(l ++ [TapeSymbol.blank]).getD i TapeSymbol.blank =
l.getD i TapeSymbol.blank := by
induction l generalizing i with
| nil => cases i <;> rfl
| cons c l ih => cases i with
| zero => rfl
| succ i => exact ih i
/-- A terminating blank in the representation is invisible. -/
theorem agree_trailing_blank (t : Nat) (L c : List TapeSymbol) :
TapeAgree t (cellsTape L (c ++ [TapeSymbol.blank])) (cellsTape L c) := by
refine ⟨?_, fun i _ => rfl, fun i _ => ?_⟩
· cases c with
| nil => rfl
| cons a c => rfl
· show ((c ++ [TapeSymbol.blank]).tail).getD i TapeSymbol.blank =
(c.tail).getD i TapeSymbol.blank
cases c with
| nil => cases i <;> rfl
| cons a c => exact getD_append_blank c i
/-- **The round's tapes are the clean ones, as far as the delegate can see.** -/
theorem roundTapes_agree (B : Nat) (Ld : Fin 4 → List TapeSymbol)
(xs : Fin 3 → List TapeSymbol) (m : Nat) (j : Fin 4)
(L' : List TapeSymbol)
(hLd : Ld j = List.replicate B TapeSymbol.blank ++ L') :
TapeAgree (B + 1) (roundTapes Ld xs m j)
(cellsTape [] (roundContent xs m j)) := by
refine TapeAgree.trans ?_ (agree_trailing_blank (B + 1) []
(roundContent xs m j))
show TapeAgree (B + 1)
(cellsTape (TapeSymbol.blank :: Ld j)
(roundContent xs m j ++ [TapeSymbol.blank])) _
rw [hLd]
exact agree_of_blank_margin B L' (roundContent xs m j ++ [TapeSymbol.blank])
(B + 1) (by omega)
end SipserGacsLautemann