sgl_body_spec
DefinitionDefinition code
import Definitions.Def_sgl_body_tapes
/-!
# One loop body, end to end
Four stages chained with `chainStepC`: the round, the bump, the guide step, the
test. What makes this more than a chain is that the body must report *two*
answers — the delegate's verdict and whether offsets remain — and a composition
only carries its last stage's verdict. The second answer is recovered from the
terminal state by peeling the `andThen` layers, which is what `loopBody_reads'`
does.
The cost is the round's plus eight: one step for the composition's own
dispatch at each of the three joins, three for the bump, one for the guide step
and one for the test.
-/
namespace SipserGacsLautemann
open Classical
variable {n states : Nat}
set_option maxHeartbeats 4000000 in
/-- **One body of the offset scheduler.** From the invariant at round `r`, the
body halts reporting whether offsets remain, its terminal state carries the
delegate's verdict, and its tapes satisfy the invariant at round `r + 1`. -/
theorem loopBody_spec (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) (T : Fin n → Tape)
(xs Ls Rs : Fin 3 → List TapeSymbol) (Lclk Lg Rg : List TapeSymbol)
(R A r Tm : Nat) (Ld : Fin 4 → List TapeSymbol) (v : Bool)
(hxs : ∀ i, ∀ x ∈ xs i, x ≠ TapeSymbol.blank)
(hinv : OffsetInv L gd xs Ls Rs Lclk Lg Rg R A r T)
(hr : r < R) (hA : 1 ≤ A)
(hsize : ∀ j, (roundContent xs r j).length + 2 ≤ A + A)
(hdst : ∀ j, ((moveDir HeadMove.right)^[A + A]) (T (L.dst j)) =
cellsTape (TapeSymbol.blank :: Ld j) [])
(hlive : ∀ m, m < Tm → M.result
((M.step^[m]) ⟨M.start, roundTapes Ld xs r⟩).state = none)
(hhalt : M.result
((M.step^[Tm]) ⟨M.start, roundTapes Ld xs r⟩).state = some v) :
∃ cost : Nat,
cost ≤ 80 * A + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
+ 13 * r + Tm + 178 ∧
HaltsExactly (loopBody L gd M) ((loopBody L gd M).startCfg T) cost
(decide (r + 1 < R)) ∧
OffsetInv L gd xs Ls Rs Lclk Lg Rg R (A + Tm) (r + 1)
(((loopBody L gd M).step^[cost]) ((loopBody L gd M).startCfg T)).tape ∧
roundVerdict (((loopBody L gd M).step^[cost])
((loopBody L gd M).startCfg T)).state = v ∧
guideLeft (((loopBody L gd M).step^[cost])
((loopBody L gd M).startCfg T)).state = decide (r + 1 < R) := by
classical
have hlen : (List.replicate r (TapeSymbol.bit true)).length = r := by simp
have hcm : ∀ x ∈ List.replicate r (TapeSymbol.bit true),
x ≠ TapeSymbol.blank := by
intro x hx
rw [List.eq_of_mem_replicate hx]
simp
-- 1. the round
obtain ⟨c1, hc1b, g1, s1⟩ := offsetRound_specB L hL hsc M T A Lclk xs Ls Rs
(List.replicate r (TapeSymbol.bit true))
(List.replicate (R - r) TapeSymbol.blank) [] Ld Tm v hxs hcm
hinv.clk hinv.src hinv.cnt hdst (by rw [hlen]; exact hlive)
(by rw [hlen]; exact hhalt)
rw [hlen] at hc1b s1
set W := ((M.step^[Tm]) ⟨M.start, roundTapes Ld xs r⟩).tape with hW
set T1 := clockTapesL L.sel L.clk T W (roundClockLeft A Lclk) Tm with hT1
have hnosel : ∀ i : Fin n, (∀ j, L.dst j ≠ i) → ¬ ∃ j, L.sel j = i := by
intro i hi hex
obtain ⟨j, hj⟩ := hex
exact hi j hj
-- 2. the counter is where the round left it
have hT1cnt : T1 L.cnt = cellsTape
(TapeSymbol.blank :: List.replicate (R - r) TapeSymbol.blank)
(List.replicate r (TapeSymbol.bit true) ++ [TapeSymbol.blank]) := by
rw [hT1, clockTapesL_outer L.sel L.clk T W _ Tm L.cnt
(fun h => hL.clk_cnt h.symm) (hnosel _ (fun j => hL.cnt_dst j))]
exact hinv.cnt
obtain ⟨g2, s2⟩ := bumpCounter_spec L.cnt r
(List.replicate (R - r) TapeSymbol.blank) [] T1 hT1cnt
set T2 := Function.update T1 L.cnt
(cellsTape (List.replicate (R - r) TapeSymbol.blank)
(List.replicate (r + 1) (TapeSymbol.bit true) ++
TapeSymbol.blank :: [])) with hT2
-- 3. the guide has not moved yet
have hT2gd : T2 gd = T gd := by
rw [hT2, Function.update_of_ne hgn, hT1,
clockTapesL_outer L.sel L.clk T W _ Tm gd hgc
(hnosel _ (fun j => fun hcon => hgd j hcon.symm))]
have g3 := moveUpTo_spec gd 1 HeadMove.right (by omega) T2
set T3 := Function.update T2 gd (moveDir HeadMove.right (T gd)) with hT3
have s3 : (((moveUpTo gd 1 HeadMove.right).step^[1])
((moveUpTo gd 1 HeadMove.right).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape gd 1 HeadMove.right (by omega) T2, hT3,
Function.iterate_one, hT2gd]
-- 4. the invariant one round on, and what the test reads
have hinv3 : OffsetInv L gd xs Ls Rs Lclk Lg Rg R (A + Tm) (r + 1) T3 :=
offsetInv_succ L hL gd hgc hgd hgn hgs hsc hsn xs Ls Rs Lclk Lg Rg
R A r Tm T Ld M hinv hr hA hsize T3 (by rw [hT3, hT2, hT1])
have hread : notBlankAt gd (fun i => (T3 i).head) = decide (r + 1 < R) :=
guide_test L gd xs Ls Rs Lclk Lg Rg R (A + Tm) r T3 hinv3
have g4 := TypedMachine.test_spec (notBlankAt gd) T3
rw [hread] at g4
-- 5. the chain
have k3 := chainStepC g3 s3 g4
have k2 := chainStepC g2 s2 k3.1
have k1 := chainStepC g1 s1 k2.1
have hfin := k1.2
rw [show ((offsetRound L M).andThen fun _ =>
(bumpCounter L.cnt).andThen fun _ =>
(moveUpTo gd 1 HeadMove.right).andThen fun _ =>
TypedMachine.test (notBlankAt gd)) = loopBody L gd M from rfl] at hfin
have hIR : ∀ {S₁ S₂ : Type} (b : Bool) (c : TypedConfiguration n S₂),
(TypedConfiguration.inRight (S₁ := S₁) b c).tape = c.tape :=
fun _ _ => rfl
have htape : (((loopBody L gd M).step^[c1 + 1 + (1 + 1 + 1 + 1 + (1 + 1 + 1))])
((loopBody L gd M).startCfg T)).tape = T3 := by
rw [hfin, hIR, k2.2, hIR, k3.2, hIR, TypedMachine.test_tape]
have hpeel := loopBody_reads' (S₁ := Fin states) v true true
(decide (r + 1 < R)) _ _ _ k3.2 k2.2
(by rw [test_state]; exact congrArg some hread)
refine ⟨c1 + 1 + (1 + 1 + 1 + 1 + (1 + 1 + 1)), by omega, k1.1, ?_, ?_, ?_⟩
· rw [htape]; exact hinv3
· rw [hfin]; exact hpeel.1
· rw [hfin]; exact hpeel.2
end SipserGacsLautemann