sgl_offset_answer
DefinitionDefinition code
import Definitions.Def_sgl_sched_layout
/-!
# What the delegate actually answers
The round hands its delegate tapes whose *left* context is whatever the
previous round left behind. The round is faithful either way — it reports the
delegate's verdict on the tapes it was given — but a caller wants the verdict
to be a function of the offset alone, not of the accumulated debris. So the
delegate's interface has to say that: one answer per offset, uniformly in the
debris.
That is a real obligation on whoever supplies the delegate, and naming it here
is the honest place to put it. A machine that never steps left of its origin
satisfies it vacuously, since the debris always sits behind a blank.
Given the interface, the trajectory's chosen verdict is that answer. As with
the cost bound, the identification is by uniqueness rather than by threading:
the recorded round and a fresh appeal to the delegate halt at the same step,
so they have the same terminal state, so they report the same verdict.
-/
namespace SipserGacsLautemann
open Classical
variable {n states : Nat}
/-- The delegate answers `ans m` at offset `m`, within `B` steps, whatever
debris precedes its tapes. -/
def RoundUniform (M : Machine 4 states) (xs : Fin 3 → List TapeSymbol)
(B : Nat) (ans : Nat → Bool) : Prop :=
∀ (Ld : Fin 4 → List TapeSymbol) (m : Nat), ∃ Tm : Nat,
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 (ans m)
theorem roundHaltingBy_of_uniform {M : Machine 4 states}
{xs : Fin 3 → List TapeSymbol} {B : Nat} {ans : Nat → Bool}
(h : RoundUniform M xs B ans) : RoundHaltingBy M xs B := by
intro Ld m
obtain ⟨Tm, hB, hlive, hhalt⟩ := h Ld m
exact ⟨Tm, ans m, hB, 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)
set_option maxHeartbeats 1000000 in
/-- **The recorded verdict is the delegate's answer.** -/
theorem ostep_answer (B : Nat) (ans : Nat → Bool)
(hU : RoundUniform M xs B ans)
(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).2.2.1 = ans i := by
classical
subst hti
obtain ⟨Ld, hdst⟩ := t.hinv.dstFun
obtain ⟨Tm, hTmB, hlive, hhalt⟩ := hU 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 (ans t.idx) 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, hrv2, hgl2⟩ := 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
rw [← hrv2, hcost]
exact hrv
/-- The same, along the trajectory. -/
theorem oans_eq (B : Nat) (ans : Nat → Bool) (hU : RoundUniform M xs B ans)
(s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
(i : Nat) (hi : i < R) :
oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = ans i :=
ostep_answer L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B ans hU (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) i
(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)) hi
/-- **The scheduler's verdict, in the delegate's own terms.** -/
theorem offsetLoop_answer (B : Nat) (ans : Nat → Bool)
(hU : RoundUniform M xs B ans)
(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 ∧ ans i = true)) := by
classical
obtain ⟨cost, hb, hloop⟩ := offsetLoop_cost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B
(roundHaltingBy_of_uniform hU) s₀ h0 hR
refine ⟨cost, hb, ?_⟩
have hiff : (∃ 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) ↔
(∃ i, i < R ∧ ans i = true) := by
constructor
· rintro ⟨i, hi, hv⟩
exact ⟨i, hi, by rw [← oans_eq L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B ans hU s₀ h0 i hi]; exact hv⟩
· rintro ⟨i, hi, hv⟩
exact ⟨i, hi, by rw [oans_eq L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B ans hU s₀ h0 i hi]; exact hv⟩
rw [decide_eq_decide.mpr hiff] at hloop
exact hloop
end
end SipserGacsLautemann