sgl_offset_traj
DefinitionDefinition code
import Definitions.Def_sgl_body_spec
/-!
# The scheduler's trajectory
`loopBody_spec` describes one round from an invariant to the next. To feed
`loopState_spec_v` the rounds have to be laid out as functions of the round
index, which means bundling everything a round needs into a single carrier and
stepping it.
The carrier holds the clock count, the round index, the tapes, and the four
facts a round consumes. Only the clock and the index move; the size
side-conditions are stated against `R` and the input lengths rather than the
current round, so they survive a step by monotonicity alone — the clock only
grows. That is the whole reason for stating them that way: a side-condition
phrased in terms of `r` would have to be re-proved every round, and at `r = R`
it would be false.
-/
namespace SipserGacsLautemann
open Classical
variable {n states : Nat}
/-- The per-round size bound, from the two bounds the carrier holds. -/
theorem roundContent_size (xs : Fin 3 → List TapeSymbol) (R A r : Nat)
(hr : r ≤ R) (hsz : ∀ i : Fin 3, (xs i).length + 2 ≤ A + A)
(hszR : R + 2 ≤ A + A) :
∀ j, (roundContent xs r j).length + 2 ≤ A + A := by
intro j
rw [roundContent]
by_cases h : j.val < 3
· rw [dif_pos h]
exact hsz _
· rw [dif_neg h, List.length_replicate]
omega
/-- **Everything a round of the scheduler stands on.** -/
structure OState (L : RoundLayout n) (gd : Fin n)
(xs Ls Rs : Fin 3 → List TapeSymbol) (Lclk Lg Rg : List TapeSymbol)
(R : Nat) : Type where
clock : Nat
idx : Nat
tp : Fin n → Tape
hA : 1 ≤ clock
hsz : ∀ i : Fin 3, (xs i).length + 2 ≤ clock + clock
hszR : R + 2 ≤ clock + clock
hinv : OffsetInv L gd xs Ls Rs Lclk Lg Rg R clock idx tp
/-- The delegate halts on every round's input. This is what it means for `M`
to be a decider, in the only form the scheduler uses. -/
def RoundHalting (M : Machine 4 states) (xs : Fin 3 → List TapeSymbol) : Prop :=
∀ (Ld : Fin 4 → List TapeSymbol) (m : Nat), ∃ Tm : Nat, ∃ v : Bool,
(∀ 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
set_option maxHeartbeats 1000000 in
/-- **One step of the trajectory.** From a carrier at round `r < R` there is a
cost, a delegate step count, a delegate verdict and a successor carrier, with
the body halting exactly as the loop needs to read it. -/
theorem ostep_exists (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)
(s : OState L gd xs Ls Rs Lclk Lg Rg R) (hidx : s.idx < R) :
∃ p : Nat × Nat × Bool × OState L gd xs Ls Rs Lclk Lg Rg R,
p.1 ≤ 80 * s.clock + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
+ 13 * s.idx + p.2.1 + 178 ∧
p.2.2.2.clock = s.clock + p.2.1 ∧
p.2.2.2.idx = s.idx + 1 ∧
HaltsExactly (loopBody L gd M) ((loopBody L gd M).startCfg s.tp) p.1
(decide (s.idx + 1 < R)) ∧
p.2.2.2.tp = (((loopBody L gd M).step^[p.1])
((loopBody L gd M).startCfg s.tp)).tape ∧
roundVerdict (((loopBody L gd M).step^[p.1])
((loopBody L gd M).startCfg s.tp)).state = p.2.2.1 ∧
guideLeft (((loopBody L gd M).step^[p.1])
((loopBody L gd M).startCfg s.tp)).state = decide (s.idx + 1 < R) := by
classical
obtain ⟨Ld, hdst⟩ := s.hinv.dstFun
obtain ⟨Tm, v, hlive, hhalt⟩ := hhalts Ld s.idx
obtain ⟨cost, hcb, hhaltsB, hinv', hrv, hgl⟩ :=
loopBody_spec L hL gd hgc hgd hgn hgs hsc hsn M s.tp xs Ls Rs Lclk Lg Rg
R s.clock s.idx Tm Ld v hxs s.hinv hidx s.hA
(roundContent_size xs R s.clock s.idx (le_of_lt hidx) s.hsz s.hszR)
hdst hlive hhalt
refine ⟨⟨cost, Tm, v,
{ clock := s.clock + Tm
idx := s.idx + 1
tp := (((loopBody L gd M).step^[cost])
((loopBody L gd M).startCfg s.tp)).tape
hA := by have := s.hA; omega
hsz := by intro i; have := s.hsz i; omega
hszR := by have := s.hszR; omega
hinv := hinv' }⟩, hcb, rfl, rfl, hhaltsB, rfl, hrv, hgl⟩
end SipserGacsLautemann