sgl_offset_cost
DefinitionDefinition code
import Definitions.Def_sgl_offset_loop_spec
/-!
# What the scheduler costs
The trajectory's per-round data is picked by `choose`, so the delegate's step
count at round `i` is not literally the one a fresh appeal to the delegate's
time bound produces. It is nonetheless the same number, and the reason is
worth naming: `HaltsExactly` pins the step count exactly, so the recorded cost
is *the* halting time and no other; and the round's own invariant pins the
clock's mark count to the tape, so the recorded step count is *the* count the
clock actually holds. Both are recovered by uniqueness rather than by
threading, which is why the loop could be built before the bound existed.
The bound itself is then the expected shape: every round costs the round's
`80·A + 13·Σ|xs| + 13·r + Tm + 178`, the clock `A` never exceeds its start plus
`R·B`, and there are at most `R` rounds.
-/
namespace SipserGacsLautemann
open Classical
variable {tapes n states : Nat} {S : Type}
/-- A machine halts at one time only. -/
theorem HaltsExactly.unique {body : TypedMachine tapes S}
{c : TypedConfiguration tapes S} {a b : Nat} {v w : Bool}
(h₁ : HaltsExactly body c a v) (h₂ : HaltsExactly body c b w) : a = b := by
by_contra hne
rcases Nat.lt_or_ge a b with hlt | hge
· have hn := h₂.fresh a hlt
rw [h₁.halts] at hn
simp at hn
· have hlt : b < a := by omega
have hn := h₁.fresh b hlt
rw [h₂.halts] at hn
simp at hn
/-- The clock's mark count is visible in its tape. -/
theorem clockCount_inj (a b : Nat) (Lc : List TapeSymbol)
(h : cellsTape (List.replicate a (TapeSymbol.bit true) ++
TapeSymbol.blank :: Lc) [] =
cellsTape (List.replicate b (TapeSymbol.bit true) ++
TapeSymbol.blank :: Lc) []) : a = b := by
have hl : (List.replicate a (TapeSymbol.bit true) ++
TapeSymbol.blank :: Lc).length =
(List.replicate b (TapeSymbol.bit true) ++
TapeSymbol.blank :: Lc).length :=
congrArg List.length (congrArg Tape.left h)
simpa using hl
/-- The delegate halts within `B` on every round's input. -/
def RoundHaltingBy (M : Machine 4 states) (xs : Fin 3 → List TapeSymbol)
(B : Nat) : Prop :=
∀ (Ld : Fin 4 → List TapeSymbol) (m : Nat), ∃ Tm : Nat, ∃ v : Bool,
Tm ≤ B ∧
(∀ t, t < Tm → M.result
((M.step^[t]) ⟨M.start, roundTapes Ld xs m⟩).state = none) ∧
M.result ((M.step^[Tm]) ⟨M.start, roundTapes Ld xs m⟩).state = some v
theorem roundHalting_of_by {M : Machine 4 states} {xs : Fin 3 → List TapeSymbol}
{B : Nat} (h : RoundHaltingBy M xs B) : RoundHalting M xs := by
intro Ld m
obtain ⟨Tm, v, _, hlive, hhalt⟩ := h Ld m
exact ⟨Tm, v, hlive, hhalt⟩
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)
/-- The delegate's step count at round `i`. -/
noncomputable def otime (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) :
Nat :=
(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
set_option maxHeartbeats 1000000 in
/-- **The recorded round agrees with a fresh appeal to the time bound.** Both
the cost and the delegate's step count are recovered by uniqueness. -/
theorem ostep_bound (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) :
(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1 ≤ 80 * t.clock
+ 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
+ 13 * i + B + 178 ∧
(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 ≤ B := 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⟩ :=
loopBody_spec 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 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 htape : (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 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 [htape] at h1
rw [h1] at h2
have := clockCount_inj _ _ Lclk h2.symm
refine ⟨by omega, by omega⟩
set_option maxHeartbeats 1000000 in
/-- The clock grows by at most `B` a round. -/
theorem otraj_clock (B : Nat) (hB : RoundHaltingBy M xs B)
(s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
(i : Nat) (hi : i ≤ R) :
(otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).clock ≤ s₀.clock + i * B := by
induction i with
| zero => simp [otraj]
| succ i ih =>
have hle : i ≤ R := by omega
have hilt : i < R := by omega
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 hbd := (ostep_bound L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB (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).2
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
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 ocost_le (B : Nat) (hB : RoundHaltingBy M xs B)
(s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
(i : Nat) (hi : i < R) :
ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs 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 := otraj_idx L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 i (le_of_lt hi)
have h1 := (ostep_bound L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) i hidx hi).1
have h2 := otraj_clock L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB s₀ h0 i (le_of_lt hi)
have h3 : i * B ≤ R * B := Nat.mul_le_mul_right B (le_of_lt hi)
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)).1 ≤ _
omega
set_option maxHeartbeats 1000000 in
/-- **The scheduler is polynomial.** It halts with the right answer inside a
bound built from the clock's start, the round count, the input lengths and the
delegate's own time bound. -/
theorem offsetLoop_cost (B : Nat) (hB : RoundHaltingBy M xs B)
(s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0) (hR : 1 ≤ R) :
∃ cost : Nat,
cost ≤ (R + 1) * (80 * (s₀.clock + R * B)
+ 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
+ 13 * R + B + 179) ∧
HaltsExactly (offsetLoop L gd M)
(TypedConfiguration.inLoop () (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ 0)) cost
(decide (∃ i, i < R ∧ oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = true)) := by
obtain ⟨rounds, hlt, hloop⟩ := offsetLoop_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 hR
refine ⟨_, ?_, hloop⟩
set K := 80 * (s₀.clock + R * B)
+ 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
+ 13 * R + B + 178 with hK
clear_value K
have hall : ∀ i, i < rounds → ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i ≤ K := by
intro i hi
rw [hK]
exact ocost_le L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB s₀ h0 i (by omega)
have h1 := loopCost_le_of hall
have h2 := ocost_le L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB s₀ h0 rounds hlt
have h3 : rounds * (K + 1) ≤ R * (K + 1) :=
Nat.mul_le_mul_right _ (by omega)
rw [← hK] at h2
calc loopCost (ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀) rounds + ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds
≤ rounds * (K + 1) + K := by omega
_ ≤ R * (K + 1) + (K + 1) := by omega
_ = (R + 1) * (K + 1) := (Nat.succ_mul R (K + 1)).symm
_ = (R + 1) * (80 * (s₀.clock + R * B)
+ 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
+ 13 * R + B + 179) := by rw [hK]
end
end SipserGacsLautemann