sgl_body_dst
DefinitionDefinition code
import Definitions.Def_sgl_skip_margin
/-!
# Where the delegate's tapes end up
`loopBody_spec` reports the invariant one round on, which is all the loop
needs, but it does not say *which* tapes the working roles now hold. For the
debris argument that is exactly what is wanted: the working tapes carry the
delegate's own final tapes, unchanged, so their written extent is bounded by
the delegate's step count and the next round's skip can be shown to overshoot
it by any margin the clock affords.
The proof is `loopBody_spec`'s, with the working tapes read off the round's
`clockTapesL` at the end.
-/
namespace SipserGacsLautemann
open Classical
variable {n states : Nat}
theorem loopBody_dst (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) ∧
(∀ j, (((loopBody L gd M).step^[cost])
((loopBody L gd M).startCfg T)).tape (L.dst j) =
((M.step^[Tm]) ⟨M.start, roundTapes Ld xs r⟩).tape j) := 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)
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
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
· intro j
rw [htape, hT3, Function.update_of_ne (Ne.symm (hgd j)), hT2,
Function.update_of_ne (hL.cnt_dst j), hT1]
exact clockTapesL_inner L.sel L.clk hL.sel_inj hL.sel_clk T W
(roundClockLeft A Lclk) Tm j
end SipserGacsLautemann