sgl_cost_m
DefinitionDefinition code
import Definitions.Def_sgl_loop_spec_m
/-!
# What the margin-carrying scheduler costs
Simpler than the original cost argument: the trajectory's own step lemma now
exposes the delegate's step bound directly, so it no longer has to be recovered
from the clock's mark count.
-/
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 B Q : Nat) (hxs : ∀ i, ∀ x ∈ xs i, x ≠ TapeSymbol.blank)
(hQ : ∀ m j, m ≤ R → (roundContent xs m j).length ≤ Q)
(hhalts : RoundHaltingM M xs B)
/-- The step bound and the delegate's bound, both exposed. -/
theorem ostepM_bound (t : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q) (i : Nat)
(hti : t.idx = i) (hi : i < R) :
(ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t).1 ≤ 80 * t.clock
+ 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
+ 13 * i + B + 178 ∧
(ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t).2.1 ≤ B := by
subst hti
rw [ostepM_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t hi]
have hch := (ostep_existsM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t hi).choose_spec
exact ⟨by have h1 := hch.1; have h2 := hch.2.1; omega, hch.2.1⟩
set_option maxHeartbeats 1000000 in
/-- The clock grows by at most `B` a round. -/
theorem otrajM_clock (s₀ : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q)
(h0 : s₀.idx = 0) (i : Nat) (hi : i ≤ R) :
(otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i).clock ≤ s₀.clock + i * B := by
induction i with
| zero => simp [otrajM]
| succ i ih =>
have hle : i ≤ R := by omega
have hilt : i < R := by omega
have hidx := otrajM_idx L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ h0 i hle
have hlt' : (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i).idx < R := by rw [hidx]; exact hilt
have hbd := (ostepM_bound L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i) i hidx hilt).2
have hclock : (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ (i + 1)).clock =
(otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i).clock + (ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i)).2.1 := by
show (ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i)).2.2.2.clock = _
rw [ostepM_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i) hlt']
exact (ostep_existsM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i) hlt').choose_spec.2.2.1
have hih := ih hle
have hmul : (i + 1) * B = i * B + B := by ring
omega
set_option maxHeartbeats 1000000 in
/-- Every round costs at most the same amount. -/
theorem ocostM_le (s₀ : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q)
(h0 : s₀.idx = 0) (i : Nat) (hi : i < R) :
ocostM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i ≤ 80 * (s₀.clock + R * B)
+ 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
+ 13 * R + B + 178 := by
have hidx := otrajM_idx L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ h0 i (le_of_lt hi)
have h1 := (ostepM_bound L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i) i hidx hi).1
have h2 := otrajM_clock L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ h0 i (le_of_lt hi)
have h3 : i * B ≤ R * B := Nat.mul_le_mul_right B (le_of_lt hi)
show (ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i)).1 ≤ _
omega
end
end SipserGacsLautemann