sgl_body_tapes
DefinitionDefinition code
import Definitions.Def_sgl_loop_reads
/-!
# One body's effect on the tapes
The round hands back a `clockTapesL`, the bump rewrites the counter, and the
guide step rewrites the guide. Composing those three updates and showing the
result is the invariant one round later is entirely index bookkeeping — but it
is the bookkeeping the loop stands on, so each of the five roles is discharged
separately against the re-entry lemmas.
Two distinctness facts the round's `RoundLayout.Wf` does not carry are needed
here and are not derivable from it: an input tape must differ from the counter,
and the guide must differ from everything. Both are carried explicitly, the
same way `offsetRound_spec` carries `src i ≠ clk`.
-/
namespace SipserGacsLautemann
open Classical
variable {n states : Nat}
/-- A round's tape holds exactly its content to the right of the head. -/
theorem roundTapes_right_length (Ld : Fin 4 → List TapeSymbol)
(xs : Fin 3 → List TapeSymbol) (m : Nat) (j : Fin 4) :
(roundTapes Ld xs m j).right.length = (roundContent xs m j).length := by
show ((roundContent xs m j ++ [TapeSymbol.blank]).tail).length = _
cases h : roundContent xs m j with
| nil => simp
| cons c l => simp
set_option maxHeartbeats 1000000 in
/-- **The invariant advances.** From the configuration at round `r`, the
round's delegation followed by the bump and the guide step lands on the
configuration at round `r + 1`, with the clock carrying the delegate's steps. -/
theorem offsetInv_succ (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)
(xs Ls Rs : Fin 3 → List TapeSymbol) (Lclk Lg Rg : List TapeSymbol)
(R A r Tm : Nat) (T : Fin n → Tape) (Ld : Fin 4 → List TapeSymbol)
(M : Machine 4 states)
(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)
(T3 : Fin n → Tape)
(hT3 : T3 = Function.update
(Function.update
(clockTapesL L.sel L.clk T
((M.step^[Tm]) ⟨M.start, roundTapes Ld xs r⟩).tape
(roundClockLeft A Lclk) Tm)
L.cnt (cellsTape (List.replicate (R - r) TapeSymbol.blank)
(List.replicate (r + 1) (TapeSymbol.bit true) ++
[TapeSymbol.blank])))
gd (moveDir HeadMove.right (T gd))) :
OffsetInv L gd xs Ls Rs Lclk Lg Rg R (A + Tm) (r + 1) T3 := by
classical
have hcntclk : L.cnt ≠ L.clk := fun h => hL.clk_cnt h.symm
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 ⟨?_, ?_, ?_, ?_, ?_⟩
· -- the clock
rw [hT3, Function.update_of_ne (Ne.symm hgc),
Function.update_of_ne hL.clk_cnt, clockTapesL_clk]
exact clock_reenters A Tm hA Lclk
· -- the inputs
intro i
rw [hT3, Function.update_of_ne (Ne.symm (hgs i)),
Function.update_of_ne (hsn i),
clockTapesL_outer L.sel L.clk T _ _ Tm (L.src i) (hsc i)
(hnosel _ (fun j => fun hc => hL.src_dst i j hc.symm))]
exact hinv.src i
· -- the counter
rw [hT3, Function.update_of_ne (Ne.symm hgn), Function.update_self]
exact counter_reenters R r hr
· -- the working tapes
intro j
have hval : T3 (L.dst j) =
((M.step^[Tm]) ⟨M.start, roundTapes Ld xs r⟩).tape j := by
rw [hT3, Function.update_of_ne (Ne.symm (hgd j)),
Function.update_of_ne (hL.cnt_dst j)]
exact clockTapesL_inner L.sel L.clk hL.sel_inj hL.sel_clk T _ _ Tm j
rw [hval]
refine delegate_leaves_skippable M ⟨M.start, roundTapes Ld xs r⟩ j Tm
(roundContent xs r j).length ((A + Tm) + (A + Tm)) ?_ ?_
· exact le_of_eq (roundTapes_right_length Ld xs r j)
· have := hsize j
omega
· -- the guide
rw [hT3, Function.update_self, hinv.gdt]
exact guide_reenters R r hr Lg Rg
/-- **What the loop's own test sees.** After the guide step the head carries a
mark exactly when another offset remains. -/
theorem guide_test (L : RoundLayout n) (gd : Fin n)
(xs Ls Rs : Fin 3 → List TapeSymbol) (Lclk Lg Rg : List TapeSymbol)
(R A r : Nat) (T3 : Fin n → Tape)
(hinv : OffsetInv L gd xs Ls Rs Lclk Lg Rg R A (r + 1) T3) :
notBlankAt gd (fun i => (T3 i).head) = decide (r + 1 < R) := by
have hhead := guide_head R (r + 1) Lg Rg
rw [← hinv.gdt] at hhead
by_cases hr : r + 1 < R
· rw [if_pos hr] at hhead
rw [notBlankAt_true gd T3 (by rw [hhead]; simp), decide_eq_true hr]
· rw [if_neg hr] at hhead
rw [notBlankAt_false gd T3 hhead, decide_eq_false hr]
end SipserGacsLautemann