sgl_offset_records
DefinitionDefinition code
import Definitions.Def_sgl_offset_traj
/-!
# The trajectory, and the loop's per-round records
`ostep` picks one round's data by choice and `otraj` iterates it. Past round
`R` the step is the identity, so the trajectory is total without the carrier
having to be defined at a round the invariant cannot reach.
`offsetRound_record` is then the `LoopRound` the loop wants, for any round that
both rejects and still has offsets left. Those two conditions are exactly the
loop's own stopping test read backwards, which is what makes the record and the
machine agree by construction rather than by a matching argument.
-/
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)
/-- One round's data, chosen; the identity past the last round. -/
noncomputable def ostep (s : OState L gd xs Ls Rs Lclk Lg Rg R) :
Nat × Nat × Bool × OState L gd xs Ls Rs Lclk Lg Rg R :=
if h : s.idx < R then
(ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
hxs hhalts s h).choose
else (0, 0, false, s)
theorem ostep_spec (s : OState L gd xs Ls Rs Lclk Lg Rg R) (h : s.idx < R) :
(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
hxs hhalts s) =
(ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
hxs hhalts s h).choose := by
rw [ostep, dif_pos h]
/-- The trajectory of carriers. -/
noncomputable def otraj (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) :
Nat → OState L gd xs Ls Rs Lclk Lg Rg R
| 0 => s₀
| i + 1 => (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
hxs hhalts (otraj s₀ i)).2.2.2
/-- Round `i` of the trajectory is at index `i`, as long as it is a round that
actually runs. -/
theorem otraj_idx (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).idx = i := by
induction i with
| zero => exact h0
| succ i ih =>
have hle : i ≤ R := by omega
have hidx := ih 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]; omega
rw [otraj, ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk
Lg Rg R hxs hhalts _ hlt]
have := (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk
Lg Rg R hxs hhalts _ hlt).choose_spec.2.2.1
rw [this, hidx]
/-- The per-round cost. -/
noncomputable def ocost (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)).1
/-- The delegate's verdict at round `i`. -/
noncomputable def oans (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) :
Bool :=
(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.1
/-- The loop's configuration at round `i`. -/
noncomputable def oconfig (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) :=
(loopBody L gd M).startCfg
(otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
hxs hhalts s₀ i).tp
/-! ## What one round of the trajectory records -/
set_option maxHeartbeats 1000000 in
/-- One chosen round, with the index named. Substituting the index rather
than rewriting it is what keeps the dependent `choose` term well typed. -/
theorem ostep_round (t : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat)
(hti : t.idx = i) (hi : i < R) :
HaltsExactly (loopBody L gd M) ((loopBody L gd M).startCfg t.tp)
(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1 (decide (i + 1 < R)) ∧
(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^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1])
((loopBody L gd M).startCfg t.tp)).tape ∧
roundVerdict ((((loopBody L gd M).step^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1])
((loopBody L gd M).startCfg t.tp))).state = (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.1 ∧
guideLeft ((((loopBody L gd M).step^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1])
((loopBody L gd M).startCfg t.tp))).state = decide (i + 1 < R) := by
subst hti
rw [ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t hi]
have hch := (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
exact ⟨hch.2.2.2.1, hch.2.2.2.2.1, hch.2.2.2.2.2.1, hch.2.2.2.2.2.2⟩
/-- The same, along the trajectory. -/
theorem otraj_round (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
(i : Nat) (hi : i < R) :
HaltsExactly (loopBody L gd M) (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) (ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)
(decide (i + 1 < R)) ∧
(otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (i + 1)).tp =
(((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₀ i]) (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)).tape ∧
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₀ i])
(oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i))).state = oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i ∧
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₀ i])
(oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i))).state = decide (i + 1 < R) :=
ostep_round 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) 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
/-- **A round of the loop.** Any round that rejects and still has offsets left
is a `LoopRound` for the scheduler. -/
theorem offset_record (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
(i : Nat) (hi : i + 1 < R) (hrej : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = false) :
LoopRound (fun _ : Unit => loopBody L gd M) (fun _ _ => ())
(fun _ b => roundVerdict b || !(guideLeft 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₀) i := 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 i (by omega)
refine ⟨⟨_, hhalt⟩, ?_, rfl, ?_⟩
· rw [hrv, hgl, hrej, decide_eq_true hi]
rfl
· show (loopBody L gd M).startCfg (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (i + 1)).tp = _
rw [htp]
rfl
end
end SipserGacsLautemann