sgl_offset_margin
DefinitionDefinition code
import Definitions.Def_sgl_body_dst
/-!
# The trajectory's working tapes
The same recovery as for the cost and the verdict: the round the trajectory
recorded and a fresh appeal to the delegate halt at the same step, so they have
the same tapes, so the working roles carry the delegate's own output. Nothing
new is proved about the loop — the fact was always true of it, and this is the
statement that says so.
With that, the next round's skip can be measured. The delegate's output is no
longer than its input plus its running time, so a skip of `2A` overshoots it by
`2A − |content| − Tm`, and the size side-condition is exactly what turns that
into a usable margin.
-/
namespace SipserGacsLautemann
open Classical
variable {n states : Nat}
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 recorded round's working tapes are the delegate's**, at the
delegate's own step count — which the round's invariant pins to the clock. -/
theorem ostep_dst (B : Nat) (hB : RoundHaltingBy M xs B)
(t : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) (hti : t.idx = i)
(hi : i < R) :
∃ Ld : Fin 4 → List TapeSymbol,
(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 ≤ B ∧
∀ j, (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.tp (L.dst j) =
((M.step^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1])
⟨M.start, roundTapes Ld xs i⟩).tape j := by
classical
subst hti
obtain ⟨Ld, hdst⟩ := t.hinv.dstFun
obtain ⟨Tm, v, hTmB, hlive, hhalt⟩ := hB Ld t.idx
obtain ⟨cost, hcb, hhaltsB, hinv', hrv, hgl, hdstv⟩ :=
loopBody_dst L hL gd hgc hgd hgn hgs hsc hsn M t.tp xs Ls Rs Lclk Lg Rg
R t.clock t.idx Tm Ld v hxs t.hinv hi t.hA
(roundContent_size xs R t.clock t.idx (le_of_lt hi) t.hsz t.hszR)
hdst hlive hhalt
obtain ⟨hrec, htp, _, _⟩ := ostep_round L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t t.idx rfl hi
have hcost : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1 = cost := hrec.unique hhaltsB
have hval : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.tp = (((loopBody L gd M).step^[cost])
((loopBody L gd M).startCfg t.tp)).tape := by
rw [htp, hcost]
have hclock : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.clock = t.clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 := by
rw [ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t hi]
exact (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg
R hxs hhalts t hi).choose_spec.2.1
have h1 := (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.hinv.clk
have h2 := hinv'.clk
rw [hval] at h1
rw [h1] at h2
have heq := clockCount_inj _ _ Lclk h2.symm
have hTmeq : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 = Tm := by omega
refine ⟨Ld, by omega, fun j => ?_⟩
rw [hval, hTmeq]
exact hdstv j
/-- **The margin the next skip leaves.** The delegate's output is no longer
than its input plus its running time, so a size condition with `B` to spare
turns the next round's skip into a blank margin of `B`. -/
theorem ostep_margin (B : Nat) (hB : RoundHaltingBy M xs B)
(Q : Nat) (hQ : ∀ m j, m ≤ R → (roundContent xs m j).length ≤ Q)
(t : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) (hti : t.idx = i)
(hi : i < R) (hsize : Q + B + 2 ≤ t.clock + t.clock) :
∀ j, ∃ L' : List TapeSymbol,
((moveDir HeadMove.right)^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.clock +
(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.clock])
((ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.tp (L.dst j)) =
cellsTape (TapeSymbol.blank ::
(List.replicate B TapeSymbol.blank ++ L')) [] := by
classical
obtain ⟨Ld, hTmB, hval⟩ := ostep_dst L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB t i hti hi
have hclock : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.clock = t.clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 := by
rw [ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t (by rw [hti]; exact hi)]
exact (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg
R hxs hhalts t (by rw [hti]; exact hi)).choose_spec.2.1
intro j
rw [hval j, hclock]
refine delegate_leaves_skippable_blanks M ⟨M.start, roundTapes Ld xs i⟩ j
((ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1) Q
((t.clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1) + (t.clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1)) B ?_ ?_
· rw [roundTapes_right_length]
exact hQ i j (le_of_lt hi)
· omega
end
end SipserGacsLautemann