The dilation round
Definitionsgl_dilation_bodycomplexity-theoryinfrastructuretheoretical-computer-scienceturing-machines
One whole round in both variants: a bit round harvests the next input cell and re-establishes the layout invariant with that cell's block appended, in at most steps; the exit round finds blank and appends the flag-clear exit block in at most 48. In both, the captured symbol is read off the terminal control state by a generic peel — which is exactly what drives the loop's stop condition, so the body needs no internal branching and every round runs the same seven stages.
Definition code
import Definitions.Def_sgl_dilation_exit
/-!
# The dilation round
One whole round in both variants: harvest a cell and append its block, or
find blank and append the exit block. The captured symbol is readable off the
terminal control state, which is what drives the loop's stop condition.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## One whole round -/
set_option maxHeartbeats 4000000 in
/-- **A bit round**: harvest the next input cell, re-establish the invariant
with its block appended. The captured symbol is readable off the terminal
state, so the loop continues. -/
theorem dilBody_spec_bit (i : Fin tapes) (first x : Bool)
(done : List Block) (rest : List Bool) (G : List TapeSymbol)
(T : Fin tapes → Tape) (hG : AllBlank G)
(hT : T i = dilTape done (x :: rest) G) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
cost ≤ 15 * rest.length + 48 ∧
HaltsExactly (dilBody i first) ((dilBody i first).startCfg T) cost true ∧
stateRead ((((dilBody i first).step^[cost])
((dilBody i first).startCfg T)).state) = some (TapeSymbol.bit x) ∧
(((dilBody i first).step^[cost])
((dilBody i first).startCfg T)).tape =
Function.update T i (dilTape (done ++ [inputBlock x first]) rest G') := by
classical
set L0 := (encodeBlocks done).reverse ++ [TapeSymbol.blank] with hL0
-- ----- stage A: five right, over the separators -----
have hA := moveUpTo_spec i 5 HeadMove.right (by omega) T
set T1 := Function.update T i
(cellsTape (List.replicate 5 TapeSymbol.blank ++ L0)
(TapeSymbol.bit x :: (bitCells rest ++ G))) with hT1
have hAt : (((moveUpTo i 5 HeadMove.right).step^[5])
((moveUpTo i 5 HeadMove.right).startCfg T)).tape = T1 := by
rw [moveUpTo_tape i 5 HeadMove.right (by omega) T, hT1]
congr 1
have hadv := cellsTape_advance (List.replicate 5 TapeSymbol.blank)
((encodeBlocks done).reverse ++ [TapeSymbol.blank])
(bitCells (x :: rest) ++ G)
have hadv' : ((moveDir HeadMove.right)^[5])
(cellsTape ((encodeBlocks done).reverse ++ [TapeSymbol.blank])
(List.replicate 5 TapeSymbol.blank ++ (bitCells (x :: rest) ++ G))) =
cellsTape (List.replicate 5 TapeSymbol.blank ++
((encodeBlocks done).reverse ++ [TapeSymbol.blank]))
(bitCells (x :: rest) ++ G) := by
simpa using hadv
rw [hT, dilTape, List.append_assoc, hadv']
rfl
have hT1i : T1 i = cellsTape (List.replicate 5 TapeSymbol.blank ++ L0)
(TapeSymbol.bit x :: (bitCells rest ++ G)) := by
rw [hT1]; simp
-- ----- stage B: the erasing read -----
set prog := (fun syms : Fin tapes → TapeSymbol =>
(syms i, fun j => (if j = i then TapeSymbol.blank else syms j,
HeadMove.stay))) with hprog
have hfires := TypedMachine.readAct_fires prog T1
have hrun1 := TypedMachine.readAct_run_one prog T1
have hst : (((TypedMachine.readAct prog).step^[1])
((TypedMachine.readAct prog).startCfg T1)).state =
some (TapeSymbol.bit x) := by
rw [hrun1]
show some ((fun j => (T1 j).head) i) = _
rw [show (fun j => (T1 j).head) i = (T1 i).head from rfl, hT1i]
rfl
set T2 := Function.update T1 i
(cellsTape (List.replicate 5 TapeSymbol.blank ++ L0)
(TapeSymbol.blank :: bitCells rest ++ G)) with hT2
have htp : (((TypedMachine.readAct prog).step^[1])
((TypedMachine.readAct prog).startCfg T1)).tape = T2 := by
rw [hrun1]
show applyAction T1 (fun syms => (prog syms).2) = _
rw [show (fun syms : Fin tapes → TapeSymbol => (prog syms).2) =
(fun syms j => (if j = i then TapeSymbol.blank else syms j,
HeadMove.stay)) from rfl]
rw [applyAction_erase, hT2]
congr 1
rw [hT1i, write_cellsTape]
rfl
have hT2i : T2 i = cellsTape (List.replicate 5 TapeSymbol.blank ++ L0)
(TapeSymbol.blank :: bitCells rest ++ G) := by
rw [hT2]; simp
-- ----- the chain -----
obtain ⟨cc, G', hG', hccb, hcc, hcct⟩ :=
dilCont_spec_bit i first x done rest G T2 hG (by rw [hT2i, hL0])
have hmain := chainStepS (M₂ := fun rec => dilCont i rec first)
hfires.fires hfires.fresh hst htp hcc
have hfull := chainStepC hA hAt hmain.1
refine ⟨5 + 1 + (1 + 1 + cc), G', hG', by omega, hfull.1, ?_, ?_⟩
· have hfin := hfull.2
rw [hmain.2] at hfin
have hfin' : ((dilBody i first).step^[5 + 1 + (1 + 1 + cc)])
((dilBody i first).startCfg T) = _ := hfin
rw [hfin']
rfl
· have hfin := hfull.2
rw [hmain.2] at hfin
have hfin' : ((dilBody i first).step^[5 + 1 + (1 + 1 + cc)])
((dilBody i first).startCfg T) = _ := hfin
rw [hfin']
show (((dilCont i (some (TapeSymbol.bit x)) first).step^[cc])
((dilCont i (some (TapeSymbol.bit x)) first).startCfg T2)).tape = _
rw [hcct, hT2, hT1]
simp only [Function.update_idem]
rw [dilTape]
set_option maxHeartbeats 4000000 in
/-- **The exit round**: the read finds blank, the chain writes the exit
block, and the captured blank is readable off the terminal state, so the
loop stops. -/
theorem dilBody_spec_blank (i : Fin tapes) (first : Bool)
(done : List Block) (G : List TapeSymbol)
(T : Fin tapes → Tape) (hG : AllBlank G)
(hT : T i = dilTape done [] G) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
cost ≤ 48 ∧
HaltsExactly (dilBody i first) ((dilBody i first).startCfg T) cost true ∧
stateRead ((((dilBody i first).step^[cost])
((dilBody i first).startCfg T)).state) = some TapeSymbol.blank ∧
(((dilBody i first).step^[cost])
((dilBody i first).startCfg T)).tape =
Function.update T i
(dilTape (done ++ [blockFor (some TapeSymbol.blank) first]) []
G') := by
classical
set L0 := (encodeBlocks done).reverse ++ [TapeSymbol.blank] with hL0
have hGt : AllBlank G.tail := fun c hc => hG c (List.mem_of_mem_tail hc)
-- ----- stage A: five right -----
have hA := moveUpTo_spec i 5 HeadMove.right (by omega) T
set T1 := Function.update T i
(cellsTape (List.replicate 5 TapeSymbol.blank ++ L0) G) with hT1
have hAt : (((moveUpTo i 5 HeadMove.right).step^[5])
((moveUpTo i 5 HeadMove.right).startCfg T)).tape = T1 := by
rw [moveUpTo_tape i 5 HeadMove.right (by omega) T, hT1]
congr 1
have hadv := cellsTape_advance (List.replicate 5 TapeSymbol.blank)
((encodeBlocks done).reverse ++ [TapeSymbol.blank]) G
have hadv' : ((moveDir HeadMove.right)^[5])
(cellsTape ((encodeBlocks done).reverse ++ [TapeSymbol.blank])
(List.replicate 5 TapeSymbol.blank ++ G)) =
cellsTape (List.replicate 5 TapeSymbol.blank ++
((encodeBlocks done).reverse ++ [TapeSymbol.blank])) G := by
simpa using hadv
rw [hT, dilTape]
rw [show List.replicate 5 TapeSymbol.blank ++ bitCells [] ++ G =
List.replicate 5 TapeSymbol.blank ++ G by simp]
rw [hadv']
have hT1i : T1 i =
cellsTape (List.replicate 5 TapeSymbol.blank ++ L0) G := by
rw [hT1]; simp
-- ----- stage B: the erasing read -----
set prog := (fun syms : Fin tapes → TapeSymbol =>
(syms i, fun j => (if j = i then TapeSymbol.blank else syms j,
HeadMove.stay))) with hprog
have hfires := TypedMachine.readAct_fires prog T1
have hrun1 := TypedMachine.readAct_run_one prog T1
have hst : (((TypedMachine.readAct prog).step^[1])
((TypedMachine.readAct prog).startCfg T1)).state =
some TapeSymbol.blank := by
rw [hrun1]
show some ((fun j => (T1 j).head) i) = _
rw [show (fun j => (T1 j).head) i = (T1 i).head from rfl, hT1i,
cellsTape_head_allBlank _ G hG]
set T2 := Function.update T1 i
(cellsTape (List.replicate 5 TapeSymbol.blank ++ L0)
(TapeSymbol.blank :: G.tail)) with hT2
have htp : (((TypedMachine.readAct prog).step^[1])
((TypedMachine.readAct prog).startCfg T1)).tape = T2 := by
rw [hrun1]
show applyAction T1 (fun syms => (prog syms).2) = _
rw [show (fun syms : Fin tapes → TapeSymbol => (prog syms).2) =
(fun syms j => (if j = i then TapeSymbol.blank else syms j,
HeadMove.stay)) from rfl]
rw [applyAction_erase, hT2]
congr 1
rw [hT1i, write_cellsTape]
have hT2i : T2 i = cellsTape (List.replicate 5 TapeSymbol.blank ++ L0)
(TapeSymbol.blank :: G.tail) := by
rw [hT2]; simp
-- ----- the chain -----
obtain ⟨cc, G', hG', hccb, hcc, hcct⟩ :=
dilCont_spec_blank i first done G.tail T2 hGt (by rw [hT2i, hL0])
have hmain := chainStepS (M₂ := fun rec => dilCont i rec first)
hfires.fires hfires.fresh hst htp hcc
have hfull := chainStepC hA hAt hmain.1
refine ⟨5 + 1 + (1 + 1 + cc), G', hG', by omega, hfull.1, ?_, ?_⟩
· have hfin := hfull.2
rw [hmain.2] at hfin
have hfin' : ((dilBody i first).step^[5 + 1 + (1 + 1 + cc)])
((dilBody i first).startCfg T) = _ := hfin
rw [hfin']
rfl
· have hfin := hfull.2
rw [hmain.2] at hfin
have hfin' : ((dilBody i first).step^[5 + 1 + (1 + 1 + cc)])
((dilBody i first).startCfg T) = _ := hfin
rw [hfin']
show (((dilCont i (some TapeSymbol.blank) first).step^[cc])
((dilCont i (some TapeSymbol.blank) first).startCfg T2)).tape = _
rw [hcct, hT2, hT1]
simp only [Function.update_idem]
rw [dilTape]
congr 1
end SipserGacsLautemann
Source
Round theorem for in-place dilation; builds on Def_sgl_dilation_exit.