sgl_scheduler
DefinitionDefinition code
import Definitions.Def_sgl_prologue_cost
/-!
# The scheduler
The prologue and the loop, joined. No bridge is needed between them: a
`loopState`'s start state is the pair of its initial carry and its body's start
state, and `inLoop` builds exactly that configuration, so the loop's own
`startCfg` on the prologue's output tapes *is* the configuration the loop's
specification begins from.
What comes out is a machine that, given three inputs on their tapes and seven
blank tapes, answers whether the delegate accepts at any offset up to the third
input's length — in time linear in the inputs plus the loop's own bound.
-/
namespace SipserGacsLautemann
open Classical
variable {states : Nat}
/-- The three inputs, as a family. -/
def schedInputs (x0 x1 x2 : List TapeSymbol) : Fin 3 → List TapeSymbol :=
fun i => if i.val = 0 then x0 else if i.val = 1 then x1 else x2
/-- Prologue, then loop. -/
noncomputable def scheduler (M : Machine 4 states) :=
(prologue (schedIdx 0) (schedIdx 1) (schedIdx 2) (schedIdx 3) (schedIdx 4)
(schedIdx 5) (schedIdx 6)).andThen fun _ =>
offsetLoop schedLayout schedGuide M
set_option maxHeartbeats 4000000 in
/-- **The scheduler decides the bounded existential.** -/
theorem scheduler_spec (M : Machine 4 states) (B : Nat) (ans : Nat → Bool)
(x0 x1 x2 : List TapeSymbol) (T : Fin 10 → Tape)
(hn0 : ∀ c ∈ x0, c ≠ TapeSymbol.blank)
(hn1 : ∀ c ∈ x1, c ≠ TapeSymbol.blank)
(hn2 : ∀ c ∈ x2, c ≠ TapeSymbol.blank)
(hU : RoundUniform M (schedInputs x0 x1 x2) B ans)
(hx0 : T (schedIdx 0) = cellsTape [] x0)
(hx1 : T (schedIdx 1) = cellsTape [] x1)
(hx2 : T (schedIdx 2) = cellsTape [] x2)
(hclk : T (schedIdx 3) = cellsTape [] [])
(hgd : T (schedIdx 4) = cellsTape [] [])
(hcnt : T (schedIdx 5) = cellsTape [] [])
(hdst : ∀ j, T (schedLayout.dst j) = cellsTape [] []) :
∃ cost : Nat,
cost ≤ 50 * (x0.length + x1.length + x2.length) + 201 +
(x2.length + 1 + 1) *
(80 * ((x2.length + (x1.length + (x0.length + 2)))
+ (x2.length + 1) * B)
+ 13 * (x0.length + x1.length + x2.length)
+ 13 * (x2.length + 1) + B + 179) ∧
HaltsExactly (scheduler M) ((scheduler M).startCfg T) cost
(decide (∃ i, i < x2.length + 1 ∧ ans i = true)) := by
classical
set xs := schedInputs x0 x1 x2 with hxs
set R := x2.length + 1 with hR
set A := x2.length + (x1.length + (x0.length + 2)) with hA
obtain ⟨c1, T', hb1, g1, t1, e0, e1, e2, eclk, egd, ecnt, eoth⟩ :=
prologue_specB schedIdx schedIdx_injective x0 x1 x2 T hn0 hn1 hn2
hx0 hx1 hx2 hclk hgd hcnt
have hdisj : ∀ (j : Fin 4), schedLayout.dst j ≠ schedIdx 0 ∧
schedLayout.dst j ≠ schedIdx 1 ∧ schedLayout.dst j ≠ schedIdx 2 ∧
schedLayout.dst j ≠ schedIdx 3 ∧ schedLayout.dst j ≠ schedIdx 4 ∧
schedLayout.dst j ≠ schedIdx 5 := by
intro j
refine ⟨?_, ?_, ?_, ?_, ?_, ?_⟩ <;>
(intro hc
have := congrArg Fin.val hc
simp [schedLayout, schedIdx] at this
try omega)
have hnbx : ∀ i, ∀ c ∈ xs i, c ≠ TapeSymbol.blank := by
intro i
fin_cases i
· exact hn0
· exact hn1
· exact hn2
have hinv : OffsetInv schedLayout schedGuide xs (fun _ => []) (fun _ => [])
[] [] [] R A 0 T' := by
refine offsetInv_zero schedLayout schedGuide xs R A T' (by omega) eclk
?_ ?_ ?_ egd
· intro i
fin_cases i
· exact e0
· exact e1
· exact e2
· exact ecnt
· intro j
obtain ⟨d0, d1, d2, d3, d4, d5⟩ := hdisj j
rw [eoth _ d0 d1 d2 d3 d4 d5]
exact hdst j
set s₀ : OState schedLayout schedGuide xs (fun _ => []) (fun _ => [])
[] [] [] R :=
{ clock := A, idx := 0, tp := T', hA := by omega
hsz := by intro i; fin_cases i <;> simp [hxs, schedInputs] <;> omega
hszR := by omega
hinv := hinv } with hs₀
obtain ⟨c2, hb2, g2⟩ := offsetLoop_answer schedLayout schedLayout_wf
schedGuide schedGuide_clk schedGuide_dst schedGuide_cnt schedGuide_src
schedLayout_src_clk schedLayout_src_cnt M xs (fun _ => []) (fun _ => [])
[] [] [] R hnbx
(roundHalting_of_by (roundHaltingBy_of_uniform hU)) B ans hU s₀ rfl
(by omega)
have g2' : HaltsExactly (offsetLoop schedLayout schedGuide M)
((offsetLoop schedLayout schedGuide M).startCfg T') c2
(decide (∃ i, i < R ∧ ans i = true)) := g2
have hclock : s₀.clock = A := rfl
have hxs0 : xs 0 = x0 := rfl
have hxs1 : xs 1 = x1 := rfl
have hxs2 : xs 2 = x2 := rfl
rw [hclock, hxs0, hxs1, hxs2] at hb2
refine ⟨_, ?_, (chainStepC g1 t1 g2').1⟩
omega
end SipserGacsLautemann