sgl_traj_margin
DefinitionDefinition code
import Definitions.Def_sgl_offset_margin
/-!
# The margin, along the whole trajectory
Two facts travel together down the rounds: the clock is large enough, and the
working tapes carry a blank margin. Neither belongs to the loop's own
invariant — the published one records the working tapes' left context only up
to existence, and that context is determined by the tape, so there is no better
witness to choose. Carrying them alongside costs one induction and forks
nothing.
The base case is the easiest of the two: at round zero the working tapes have
never been written, so the skip lands with nothing but blanks behind it.
-/
namespace SipserGacsLautemann
open Classical
variable {n states : Nat}
/-- The working tapes carry `B` blanks behind the head after the skip. -/
def MarginAt (L : RoundLayout n) (B : Nat) (T : Fin n → Tape) (A : Nat) :
Prop :=
∀ j, ∃ L' : List TapeSymbol,
((moveDir HeadMove.right)^[A + A]) (T (L.dst j)) =
cellsTape (TapeSymbol.blank ::
(List.replicate B TapeSymbol.blank ++ L')) []
/-- A virgin working tape has margin to spare. -/
theorem marginAt_virgin (L : RoundLayout n) (B : Nat) (T : Fin n → Tape)
(A : Nat) (hA : B + 2 ≤ A + A)
(hT : ∀ j, T (L.dst j) = cellsTape [] []) :
MarginAt L B T A := by
intro j
refine skip_exhausts_blanks (T (L.dst j)) (A + A) B ?_
rw [hT j]
show ([] : List TapeSymbol).tail.length + B + 2 ≤ A + A
simpa using hA
section
variable (L : RoundLayout n) (hL : L.Wf) (gd : Fin n)
(hgc : gd ≠ L.clk) (hgd : ∀ j, gd ≠ L.dst j) (hgn : gd ≠ L.cnt)
(hgs : ∀ i, gd ≠ L.src i) (hsc : ∀ i, L.src i ≠ L.clk)
(hsn : ∀ i, L.src i ≠ L.cnt)
(M : Machine 4 states)
(xs Ls Rs : Fin 3 → List TapeSymbol) (Lclk Lg Rg : List TapeSymbol)
(R : Nat) (hxs : ∀ i, ∀ x ∈ xs i, x ≠ TapeSymbol.blank)
(hhalts : RoundHalting M xs)
set_option maxHeartbeats 1000000 in
/-- **The margin survives every round.** -/
theorem otraj_margin (B : Nat) (hB : RoundHaltingBy M xs B)
(Q : Nat) (hQ : ∀ m j, m ≤ R → (roundContent xs m j).length ≤ Q)
(s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
(hsz0 : Q + B + 2 ≤ s₀.clock + s₀.clock)
(hbase : MarginAt L B s₀.tp s₀.clock)
(i : Nat) (hi : i ≤ R) :
Q + B + 2 ≤ (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).clock + (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).clock ∧
MarginAt L B (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).tp (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).clock := by
induction i with
| zero => exact ⟨hsz0, hbase⟩
| succ i ih =>
have hle : i ≤ R := by omega
have hilt : i < R := by omega
obtain ⟨hsz, hm⟩ := ih hle
have hidx := otraj_idx L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 i hle
have hlt' : (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).idx < R := by rw [hidx]; exact hilt
have hclock : (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (i + 1)).clock =
(otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)).2.1 := by
show (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)).2.2.2.clock = _
rw [ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) hlt']
exact (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk
Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) hlt').choose_spec.2.1
refine ⟨by omega, ?_⟩
have := ostep_margin L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB Q hQ (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) i hidx hilt hsz
exact this
end
end SipserGacsLautemann