The dilation, end to end
Definitionsgl_dilation_mainThe dilation, end to end. dilation_spec: for every input, the machine parks the host tape on the region hosting that input beside an empty scratch track — the initialization eliminate_last_scratch_tape needs, now proved for both the empty and non-empty cases.
dilMain_spec chains the three stages (pre-pass, loop, park); dilation_spec wraps it in the top-level read that dispatches empty input to the merge-initial region through either.
Two supporting pieces. cellsTape_retreat_take is the partial retreat — crossing cells of a left context and exposing those crossed — which generalises the existing full retreat (the case ) and is what lets the parking scan verify that every cell it crosses is non-blank. And either_run_tape_* package a branch's run at the startCfg level: rewriting with them avoids forcing the elaborator to unfold a branch machine inside a goal, which otherwise blows the heartbeat budget — the same defeq discipline that has governed every junction proof in this development.
import Definitions.Def_sgl_dilation_hosts
/-!
# The dilation, end to end
Module G2's glue: pre-pass, loop, park — and the top-level dispatch.
`cellsTape_retreat_take` is the partial retreat the parking scan needs: a
retreat of `j` cells over a left context, exposing the cells crossed so far.
It generalises `cellsTape_retreat`, which is the case `j = cs.length`.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
theorem cellsTape_retreat_take :
∀ (j : Nat) (cs L R : List TapeSymbol) (r : TapeSymbol), j ≤ cs.length →
(moveDir HeadMove.left)^[j] (cellsTape (cs ++ L) (r :: R)) =
cellsTape (cs.drop j ++ L) ((cs.take j).reverse ++ r :: R) := by
intro j
induction j with
| zero => intro cs L R r _; simp
| succ j ih =>
intro cs L R r hj
obtain ⟨c, cs', rfl⟩ : ∃ c cs', cs = c :: cs' := by
cases cs with
| nil => simp at hj
| cons a t => exact ⟨a, t, rfl⟩
rw [Function.iterate_succ_apply]
rw [show (c :: cs') ++ L = c :: (cs' ++ L) from rfl]
rw [cellsTape_moveLeft]
rw [ih cs' L (r :: R) c (by simp at hj ⊢; omega)]
simp
/-- The head after a partial retreat is the last cell crossed. -/
theorem retreat_head (j : Nat) (cs L R : List TapeSymbol) (r : TapeSymbol)
(hj : j < cs.length) :
((moveDir HeadMove.left)^[j + 1] (cellsTape (cs ++ L) (r :: R))).head =
cs.get ⟨j, hj⟩ := by
rw [cellsTape_retreat_take (j + 1) cs L R r (by omega)]
have hrev : (cs.take (j + 1)).reverse =
cs.get ⟨j, hj⟩ :: (cs.take j).reverse := by
rw [show cs.take (j + 1) = cs.take j ++ [cs.get ⟨j, hj⟩] by
rw [List.take_succ]
congr 1
simp [List.getElem?_eq_getElem hj]]
simp
rw [hrev]
rfl
/-! ## Parking the finished region -/
theorem encodeBlocks_ne_blank' (blocks : List Block) :
∀ c ∈ encodeBlocks blocks, c ≠ TapeSymbol.blank :=
encodeBlocks_ne_blank blocks
set_option maxHeartbeats 4000000 in
/-- The final leftward scan parks the head at home. -/
theorem dilPark_spec (i : Fin tapes) (blocks : List Block)
(G : List TapeSymbol) (T : Fin tapes → Tape)
(hT : T i = dilTape blocks [] G) :
HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T)
((encodeBlocks blocks).length * 4 + 3) false ∧
(((scanToBlank i HeadMove.left).step^[(encodeBlocks blocks).length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T)).tape =
Function.update T i
(ParkedTape blocks (List.replicate 5 TapeSymbol.blank ++ G)) := by
classical
set cs := (encodeBlocks blocks).reverse with hcs
set d := (encodeBlocks blocks).length with hd
have hcslen : cs.length = d := by rw [hcs, hd, List.length_reverse]
have hTc : T i = cellsTape (cs ++ [TapeSymbol.blank])
(TapeSymbol.blank :: (List.replicate 4 TapeSymbol.blank ++ G)) := by
rw [hT, dilTape, hcs]
rfl
have hlt : ∀ k, k < d →
(((moveDir HeadMove.left)^[k + 1]) (T i)).head ≠ TapeSymbol.blank := by
intro k hk
rw [hTc, retreat_head k cs [TapeSymbol.blank] _ TapeSymbol.blank
(by rw [hcslen]; exact hk)]
have hmem : cs.get ⟨k, by rw [hcslen]; exact hk⟩ ∈ encodeBlocks blocks := by
have hin : cs.get ⟨k, by rw [hcslen]; exact hk⟩ ∈ cs := List.get_mem _ _
have : cs.get ⟨k, by rw [hcslen]; exact hk⟩ ∈
(encodeBlocks blocks).reverse := by
rw [← hcs]; exact hin
exact List.mem_reverse.mp this
exact encodeBlocks_ne_blank' blocks _ hmem
have heq : (((moveDir HeadMove.left)^[d + 1]) (T i)).head =
TapeSymbol.blank := by
have hpark := dilPark blocks G
rw [← hd] at hpark
rw [hT, hpark]
rfl
refine ⟨scanToBlank_spec_of i HeadMove.left T d hlt heq, ?_⟩
rw [scanToBlank_tape_of i HeadMove.left T d hlt heq, scanTapesDir]
congr 1
rw [hT]
have hpark := dilPark blocks G
rw [← hd] at hpark
exact hpark
/-! ## The non-empty path -/
set_option maxHeartbeats 4000000 in
/-- **The dilation's main path**: from the raw input tape to the parked
region hosting it. -/
theorem dilMain_spec (i : Fin tapes) (x : Bool) (rest : List Bool)
(T : Fin tapes → Tape) (hT : T i = Tape.ofBits (x :: rest)) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
HaltsExactly (dilMain i) ((dilMain i).startCfg T) cost false ∧
(((dilMain i).step^[cost]) ((dilMain i).startCfg T)).tape =
Function.update T i (ParkedTape (dilBlocks (x :: rest)) G') := by
classical
-- pre-pass
obtain ⟨cp, G₁, hG₁, -, hP, hPt⟩ := prePass_spec i x rest [] T AllBlank.nil
(by rw [hT, ofBits_eq_cellsTape]; simp)
set T1 := Function.update T i (dilTape [] (x :: rest) G₁) with hT1
have hT1i : T1 i = dilTape [] (x :: rest) G₁ := by rw [hT1]; simp
-- loop
obtain ⟨cl, G₂, hG₂, -, hL, hLt⟩ :=
dilLoop_run i (x :: rest) true [] G₁ T1 hG₁ hT1i
have hLstart : (dilLoop i).startCfg T1 =
TypedConfiguration.inLoop true ⟨(dilBody i true).start, T1⟩ := rfl
have hL' : HaltsExactly (dilLoop i) ((dilLoop i).startCfg T1) cl false := by
rw [hLstart]; exact hL
have hLt' : (((dilLoop i).step^[cl]) ((dilLoop i).startCfg T1)).tape =
Function.update T1 i (dilTape ([] ++ dilSuffix (x :: rest) true) []
G₂) := by
rw [hLstart]; exact hLt
set T2 := Function.update T i (dilTape (dilBlocks (x :: rest)) [] G₂)
with hT2
have hLt'' : (((dilLoop i).step^[cl]) ((dilLoop i).startCfg T1)).tape = T2 := by
rw [hLt', hT1, hT2]
simp only [Function.update_idem]
rw [List.nil_append, dilSuffix_nonempty_eq]
have hT2i : T2 i = dilTape (dilBlocks (x :: rest)) [] G₂ := by rw [hT2]; simp
-- park
obtain ⟨hK, hKt⟩ := dilPark_spec i (dilBlocks (x :: rest)) G₂ T2 hT2i
-- assemble
have c2 := chainStepC hL' hLt'' hK
have c1 := chainStepC hP hPt c2.1
refine ⟨cp + 1 + (cl + 1 + ((encodeBlocks (dilBlocks (x :: rest))).length
* 4 + 3)), List.replicate 5 TapeSymbol.blank ++ G₂, ?_, c1.1, ?_⟩
· intro c hc
rcases List.mem_append.mp hc with h | h
· exact List.eq_of_mem_replicate h
· exact hG₂ c h
· have hfin := c1.2
rw [c2.2] at hfin
have hfin' : ((dilMain i).step^[cp + 1 + (cl + 1 +
((encodeBlocks (dilBlocks (x :: rest))).length * 4 + 3))])
((dilMain i).startCfg T) = _ := hfin
rw [hfin']
show (((scanToBlank i HeadMove.left).step^[_])
((scanToBlank i HeadMove.left).startCfg T2)).tape = _
rw [hKt, hT2]
simp only [Function.update_idem]
/-! ## The top-level dispatch -/
theorem either_run_tape_inr {SA SB : Type} (A : TypedMachine tapes SA)
(B : TypedMachine tapes SB) (k : Nat) (T : Fin tapes → Tape) :
(((A.either B false).step^[k]) ((A.either B false).startCfg T)).tape =
((B.step^[k]) (B.startCfg T)).tape := by
have hs : (A.either B false).startCfg T =
(⟨Sum.inr B.start, T⟩ : TypedConfiguration tapes (SA ⊕ SB)) := rfl
rw [hs, TypedMachine.either_step_inr]
rfl
theorem either_run_tape_inl {SA SB : Type} (A : TypedMachine tapes SA)
(B : TypedMachine tapes SB) (k : Nat) (T : Fin tapes → Tape) :
(((A.either B true).step^[k]) ((A.either B true).startCfg T)).tape =
((A.step^[k]) (A.startCfg T)).tape := by
have hs : (A.either B true).startCfg T =
(⟨Sum.inl A.start, T⟩ : TypedConfiguration tapes (SA ⊕ SB)) := rfl
rw [hs, TypedMachine.either_step_inl]
rfl
set_option maxHeartbeats 4000000 in
/-- **The dilation, specified.** For every input, the machine parks the host
tape on the region hosting that input beside an empty scratch track. -/
theorem dilation_spec (i : Fin tapes) (xs : List Bool)
(T : Fin tapes → Tape) (hT : T i = Tape.ofBits xs) :
∃ (cost : Nat) (G : List TapeSymbol), AllBlank G ∧
HaltsExactly (dilation i) ((dilation i).startCfg T) cost
(match xs with | [] => true | _ => false) ∧
(((dilation i).step^[cost]) ((dilation i).startCfg T)).tape =
Function.update T i (ParkedTape (encodeInputBlocks xs) G) := by
classical
set prog := (fun syms : Fin tapes → TapeSymbol =>
(syms i, fun j => (syms j, HeadMove.stay))) with hprog
have hfires := TypedMachine.readAct_fires prog T
have hrun1 := TypedMachine.readAct_run_one prog T
have hst : (((TypedMachine.readAct prog).step^[1])
((TypedMachine.readAct prog).startCfg T)).state =
some ((T i).head) := by
rw [hrun1]
have htp : (((TypedMachine.readAct prog).step^[1])
((TypedMachine.readAct prog).startCfg T)).tape = T := by
rw [hrun1]
show applyAction T (fun syms => (prog syms).2) = T
funext j
simp [applyAction, hprog, Tape.write_head_self, Tape.move]
cases xs with
| nil =>
-- the read finds blank: the initial-region branch
have hhead : (T i).head = TapeSymbol.blank := by rw [hT]; rfl
have hbit : isBitO (some ((T i).head)) = false := by rw [hhead]; rfl
obtain ⟨hI, hIt⟩ := initRegion_spec i T (by rw [hT]; rfl)
have hbranch : HaltsExactly
((dilMain i).either (initRegion i) (isBitO (some ((T i).head))))
(((dilMain i).either (initRegion i)
(isBitO (some ((T i).head)))).startCfg T) 14 true := by
rw [hbit]
exact HaltsExactly.either_inr (dilMain i) false hI
have hmain := chainStepS
(M₂ := fun rec => (dilMain i).either (initRegion i) (isBitO rec))
hfires.fires hfires.fresh hst htp hbranch
refine ⟨1 + 1 + 14, [TapeSymbol.blank], AllBlank.single, hmain.1, ?_⟩
have hfin := hmain.2
have hfin' : ((dilation i).step^[1 + 1 + 14])
((dilation i).startCfg T) = _ := hfin
rw [hfin']
show (((((dilMain i).either (initRegion i)
(isBitO (some ((T i).head))))).step^[14])
((((dilMain i).either (initRegion i)
(isBitO (some ((T i).head))))).startCfg T)).tape = _
rw [hbit, either_run_tape_inr, hIt]
rfl
| cons x rest =>
-- the read finds a bit: the main path
have hhead : (T i).head = TapeSymbol.bit x := by rw [hT]; rfl
have hbit : isBitO (some ((T i).head)) = true := by rw [hhead]; rfl
obtain ⟨cm, G, hG, hM, hMt⟩ := dilMain_spec i x rest T hT
have hbranch : HaltsExactly
((dilMain i).either (initRegion i) (isBitO (some ((T i).head))))
(((dilMain i).either (initRegion i)
(isBitO (some ((T i).head)))).startCfg T) cm false := by
rw [hbit]
exact HaltsExactly.either_inl (initRegion i) true hM
have hmain := chainStepS
(M₂ := fun rec => (dilMain i).either (initRegion i) (isBitO rec))
hfires.fires hfires.fresh hst htp hbranch
refine ⟨1 + 1 + cm, G, hG, hmain.1, ?_⟩
have hfin := hmain.2
have hfin' : ((dilation i).step^[1 + 1 + cm])
((dilation i).startCfg T) = _ := hfin
rw [hfin']
show (((((dilMain i).either (initRegion i)
(isBitO (some ((T i).head))))).step^[cm])
((((dilMain i).either (initRegion i)
(isBitO (some ((T i).head))))).startCfg T)).tape = _
rw [hbit, either_run_tape_inl, hMt, encodeInputBlocks_cons,
dilSuffix_nonempty_eq]
end SipserGacsLautemann