sgl_offset_loop_spec
DefinitionDefinition code
import Definitions.Def_sgl_offset_records
/-!
# The scheduler halts, and reports whether any offset accepted
The loop stops on the first round that accepts, or on the last round if none
does. Both cases are the same `loopState_spec_v` application; they differ only
in which disjunct of the stopping test fires — the delegate's verdict in the
first case, the exhausted guide in the second.
The verdict the loop reports is the delegate's answer at the round it stopped
on, and that answer is `true` exactly when some offset accepts: an accepting
round halts the loop immediately, and if none accepts the last round's `false`
is what stands.
-/
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 loop, at a stopping round.** Given a round that nothing before it
accepts and that stops the loop when reached, the scheduler halts there with
that round's verdict. -/
theorem offsetLoop_at (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
(rounds : Nat) (hlt : rounds < R)
(hbefore : ∀ i, i < rounds → oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = false)
(hfire : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds = true ∨ rounds + 1 = R) :
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))
(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)
(oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds) := by
obtain ⟨hhalt, htp, hrv, hgl⟩ := otraj_round L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 rounds hlt
have hstopB : (roundVerdict (((loopBody L gd M).step^[ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds])
(oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds)).state ||
!guideLeft (((loopBody L gd M).step^[ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds])
(oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds)).state) = true := by
rw [hrv, hgl]
rcases hfire with h | h
· rw [h]
rfl
· rw [decide_eq_false (by omega : ¬ rounds + 1 < R)]
simp
have hmain := TypedMachine.loopState_spec_v
(fun _ : Unit => loopBody L gd M) (fun _ _ => ())
(fun _ b => roundVerdict b || !(guideLeft b))
(fun _ b => roundVerdict b) ()
(fun _ : Nat => ()) (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀) (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) (decide (rounds + 1 < R))
(fun i hi => offset_record L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 i (by omega) (hbefore i hi))
hhalt hstopB
have hmain' : 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))
(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)
(roundVerdict (((loopBody L gd M).step^[ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds])
(oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds)).state) := hmain
rw [hrv] at hmain'
exact hmain'
set_option maxHeartbeats 1000000 in
/-- **The scheduler.** It halts, and its verdict is whether some offset below
`R` is accepted by the delegate. -/
theorem offsetLoop_spec (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R)
(h0 : s₀.idx = 0) (hR : 1 ≤ R) :
∃ rounds : Nat, rounds < R ∧
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))
(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)
(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
classical
by_cases hacc : ∃ 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
· obtain ⟨hlt, hans⟩ := Nat.find_spec hacc
have hbef : ∀ i, i < Nat.find hacc → oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = false := by
intro i hi
have hmin := Nat.find_min hacc hi
have hiR : i < R := by omega
cases hb : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i with
| false => rfl
| true => exact absurd ⟨hiR, hb⟩ hmin
have hloop := offsetLoop_at L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 (Nat.find hacc) hlt hbef (Or.inl hans)
rw [hans] at hloop
refine ⟨Nat.find hacc, hlt, ?_⟩
rw [decide_eq_true hacc]
exact hloop
· have hans : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (R - 1) = false := by
cases hb : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (R - 1) with
| false => rfl
| true => exact absurd ⟨R - 1, by omega, hb⟩ hacc
have hbef : ∀ i, i < R - 1 → oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = false := by
intro i hi
cases hb : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i with
| false => rfl
| true => exact absurd ⟨i, by omega, hb⟩ hacc
have hloop := offsetLoop_at L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 (R - 1) (by omega) hbef
(Or.inr (by omega))
rw [hans] at hloop
refine ⟨R - 1, by omega, ?_⟩
rw [decide_eq_false hacc]
exact hloop
end
end SipserGacsLautemann