Patch runs and bounded movement
Definitionsgl_patch_runPatch runs: the edge-oblivious write pass, and the machinery that retires runtime edge tests.
The update sweep must sometimes write into a neighbouring block that does not exist yet — the flag walks off the region's edge and a fresh block must materialise. Testing for the edge at runtime would split every variant in two and force differently-shaped branches into one state type. The escape is that a normalising write pass is edge-oblivious: writing — blank becomes the written zero-code, anything written stays itself — while moving preserves an existing block exactly and builds a fresh blank-symbol block out of raw tape. Raising a flag in a neighbour is the same six-cell pass whether or not the neighbour exists.
patchRun6 runs a six-cell pass of norm/put operations as one counter machine over the fixed state , so windows with different contents share one type and the simulation can dispatch on runtime data without type trouble; moveUpTo does the same for head movement over . Both carry exact run lemmas by one induction each. patchCellsN describes a pass's output cells purely functionally, reading ops and tape with blank-padding on both sides — which is precisely what makes the materialising case and the preserving case one lemma.
Also here: HaltsExactly.andThen_full, which packages a junction's halt and final tapes in one composition step, and scanToBlank_tape_of, the parking scan's final tapes, which the navigation module's specification omitted.
import Definitions.Def_sgl_region_update
/-!
# Patch runs
Module D, fourth part: the machinery that makes the update variants uniform.
The update must sometimes write into a neighbouring block that *does not exist
yet* — the flag walks off the region's edge and a fresh block must materialise.
Testing for the edge at runtime would split every variant in two and force the
two branches into one state type. The escape is that **a normalising write
pass is edge-oblivious**: writing `normalize(cell)` — blank becomes the written
zero-code, anything written stays itself — while moving preserves an existing
block exactly and builds a fresh blank-symbol block out of raw tape. Setting a
flag in a neighbour is then the same six-cell pass whether or not the
neighbour exists, with a single `put` at the flag's offset.
Two machines and a lemma:
* `patchRun6` — a six-cell pass of `norm`/`put` operations, as one counter
machine over the *fixed* state `Fin 7`, so every window has the same type and
the simulation can dispatch on runtime data without type trouble.
* `moveUpTo` — head movement over the fixed state `Fin 13`, same reason.
* `scanToBlank_tape_of` — the final tapes of the parking scan, which the
navigation module's specification omitted.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## Composition with tape tracking -/
/-- `HaltsExactly.andThen` plus the composite's final tapes, in one step. The
chained update proofs apply this once per junction. -/
theorem HaltsExactly.andThen_full {S₁ S₂ : Type} {M₁ : TypedMachine tapes S₁}
{M₂ : Bool → TypedMachine tapes S₂} {c : TypedConfiguration tapes S₁}
{a : Nat} {b : Bool} {k : Nat} {v : Bool}
(h₁ : HaltsExactly M₁ c a b)
(h₂ : HaltsExactly (M₂ b) ((M₂ b).startCfg ((M₁.step^[a]) c).tape) k v) :
HaltsExactly (M₁.andThen M₂) (TypedConfiguration.inLeft c) (a + 1 + k) v ∧
(((M₁.andThen M₂).step^[a + 1 + k]) (TypedConfiguration.inLeft c)).tape =
(((M₂ b).step^[k])
((M₂ b).startCfg ((M₁.step^[a]) c).tape)).tape := by
refine ⟨HaltsExactly.andThen h₁ h₂, ?_⟩
rw [TypedMachine.andThen_iterate M₁ M₂ c a b h₁.halts h₁.fresh k]
rfl
/-! ## Patch operations -/
/-- Blank becomes the written zero-code; written cells stay themselves. -/
def normalizeSym : TapeSymbol → TapeSymbol
| TapeSymbol.blank => TapeSymbol.bit false
| c => c
@[simp] theorem normalizeSym_bit (b : Bool) :
normalizeSym (TapeSymbol.bit b) = TapeSymbol.bit b := rfl
@[simp] theorem normalizeSym_blank :
normalizeSym TapeSymbol.blank = TapeSymbol.bit false := rfl
theorem normalizeSym_of_ne_blank {c : TapeSymbol} (h : c ≠ TapeSymbol.blank) :
normalizeSym c = c := by
cases c with
| blank => exact absurd rfl h
| bit b => rfl
/-- One cell of an update window: keep-but-normalise, or overwrite. -/
inductive PatchOp where
| norm
| put (c : TapeSymbol)
def opValue : PatchOp → TapeSymbol → TapeSymbol
| .norm, c => normalizeSym c
| .put c, _ => c
/-- The cells a patch pass writes: driven by the pass length, reading the ops
and the tape cells with blank-padding on both. -/
def patchCellsN : Nat → List PatchOp → List TapeSymbol → List TapeSymbol
| 0, _, _ => []
| n + 1, ops, R =>
opValue (ops.headD .norm) (R.headD TapeSymbol.blank) ::
patchCellsN n ops.tail R.tail
@[simp] theorem patchCellsN_zero (ops : List PatchOp) (R : List TapeSymbol) :
patchCellsN 0 ops R = [] := rfl
@[simp] theorem patchCellsN_succ (n : Nat) (ops : List PatchOp)
(R : List TapeSymbol) :
patchCellsN (n + 1) ops R =
opValue (ops.headD .norm) (R.headD TapeSymbol.blank) ::
patchCellsN n ops.tail R.tail := rfl
theorem patchCellsN_length (n : Nat) :
∀ (ops : List PatchOp) (R : List TapeSymbol),
(patchCellsN n ops R).length = n := by
induction n with
| zero => intro ops R; rfl
| succ n ih => intro ops R; simp [patchCellsN, ih]
/-- Peeling one written cell off the end of a pass. -/
theorem patchCellsN_succ_append (m : Nat) :
∀ (ops : List PatchOp) (R : List TapeSymbol),
patchCellsN (m + 1) ops R =
patchCellsN m ops R ++
[opValue (ops.getD m .norm) ((R.drop m).headD TapeSymbol.blank)] := by
induction m with
| zero =>
intro ops R
simp [patchCellsN]
cases ops <;> rfl
| succ m ih =>
intro ops R
rw [patchCellsN_succ, ih ops.tail R.tail, patchCellsN_succ,
List.cons_append]
have h1 : ops.tail.getD m PatchOp.norm = ops.getD (m + 1) PatchOp.norm := by
cases ops <;> rfl
have h2 : R.tail.drop m = R.drop (m + 1) := by
cases R <;> simp
rw [h1, h2]
/-! ## The patch machine -/
/-- A six-cell patch pass under head `i`, moving right. The state is the fixed
`Fin 7` regardless of `ops`, so windows with different contents share one
type. -/
def patchRun6 (i : Fin tapes) (ops : List PatchOp) :
TypedMachine tapes (Fin 7) where
start := ⟨0, by omega⟩
transition := fun s symbols =>
if h : s.val < 6 then
(⟨s.val + 1, by omega⟩,
fun j =>
(if j = i then opValue (ops.getD s.val .norm) (symbols i)
else symbols j,
if j = i then HeadMove.right else HeadMove.stay))
else (s, fun j => (symbols j, HeadMove.stay))
result := fun s => if s.val = 6 then some true else none
theorem patchRun6_step (i : Fin tapes) (ops : List PatchOp)
(m : Nat) (hm : m < 6) (t : Fin tapes → Tape) :
(patchRun6 i ops).step ⟨⟨m, by omega⟩, t⟩ =
⟨⟨m + 1, by omega⟩,
Function.update t i
(Tape.move
(Tape.write (t i) (opValue (ops.getD m .norm) (t i).head))
HeadMove.right)⟩ := by
have hres : (patchRun6 i ops).result ⟨m, by omega⟩ = none := by
simp [patchRun6]
omega
simp only [TypedMachine.step, hres]
simp only [patchRun6, dif_pos hm]
congr 1
funext j
by_cases hj : j = i
· subst hj
simp
· simp [hj, Tape.write_head_self, Tape.move]
theorem patchRun6_run (i : Fin tapes) (ops : List PatchOp) (m : Nat)
(hm : m ≤ 6) (tape : Fin tapes → Tape) (L R : List TapeSymbol)
(hi : tape i = cellsTape L R) :
((patchRun6 i ops).step^[m]) ((patchRun6 i ops).startCfg tape) =
⟨⟨m, by omega⟩,
Function.update tape i
(cellsTape ((patchCellsN m ops R).reverse ++ L) (R.drop m))⟩ := by
induction m with
| zero =>
simp only [Function.iterate_zero_apply, patchCellsN_zero,
List.drop_zero, List.reverse_nil, List.nil_append, ← hi,
Function.update_eq_self]
rfl
| succ m ih =>
rw [Function.iterate_succ_apply', ih (by omega),
patchRun6_step i ops m (by omega)]
congr 1
funext j
by_cases hj : j = i
· subst hj
simp only [Function.update_self]
have hhead : (cellsTape ((patchCellsN m ops R).reverse ++ L)
(R.drop m)).head = (R.drop m).headD TapeSymbol.blank := rfl
rw [hhead, cellsTape_writeMove, patchCellsN_succ_append,
List.reverse_append, List.tail_drop]
simp
· simp [hj]
theorem patchRun6_spec (i : Fin tapes) (ops : List PatchOp)
(tape : Fin tapes → Tape) (L R : List TapeSymbol)
(hi : tape i = cellsTape L R) :
HaltsExactly (patchRun6 i ops) ((patchRun6 i ops).startCfg tape) 6
true := by
constructor
· rw [patchRun6_run i ops 6 (by omega) tape L R hi]
simp [patchRun6]
· intro j hj
rw [patchRun6_run i ops j (by omega) tape L R hi]
simp [patchRun6]
omega
theorem patchRun6_tape (i : Fin tapes) (ops : List PatchOp)
(tape : Fin tapes → Tape) (L R : List TapeSymbol)
(hi : tape i = cellsTape L R) :
(((patchRun6 i ops).step^[6]) ((patchRun6 i ops).startCfg tape)).tape =
Function.update tape i
(cellsTape ((patchCellsN 6 ops R).reverse ++ L) (R.drop 6)) := by
rw [patchRun6_run i ops 6 (by omega) tape L R hi]
/-! ## Bounded movement -/
/-- Move head `i` exactly `k ≤ 12` cells in direction `dir`, over the fixed
state `Fin 13`, so movers of different distances share one type. -/
def moveUpTo (i : Fin tapes) (k : Nat) (dir : HeadMove) :
TypedMachine tapes (Fin 13) where
start := ⟨0, by omega⟩
transition := fun s symbols =>
if h : s.val < min k 12 then
(⟨s.val + 1, by omega⟩,
fun j => (symbols j, if j = i then dir else HeadMove.stay))
else (s, fun j => (symbols j, HeadMove.stay))
result := fun s => if s.val = min k 12 then some true else none
theorem moveUpTo_step (i : Fin tapes) (k : Nat) (dir : HeadMove)
(m : Nat) (hm : m < min k 12) (t : Fin tapes → Tape) :
(moveUpTo i k dir).step ⟨⟨m, by omega⟩, t⟩ =
⟨⟨m + 1, by omega⟩, Function.update t i (moveDir dir (t i))⟩ := by
have hres : (moveUpTo i k dir).result ⟨m, by omega⟩ = none := by
simp [moveUpTo]
omega
simp only [TypedMachine.step, hres]
simp only [moveUpTo, dif_pos hm]
congr 1
funext j
by_cases hj : j = i
· subst hj
simp [moveDir, Tape.write_head_self]
· simp [hj, Tape.write_head_self, Tape.move]
theorem moveUpTo_run (i : Fin tapes) (k : Nat) (dir : HeadMove) (m : Nat)
(hm : m ≤ min k 12) (tape : Fin tapes → Tape) :
((moveUpTo i k dir).step^[m]) ((moveUpTo i k dir).startCfg tape) =
⟨⟨m, by omega⟩,
Function.update tape i ((moveDir dir)^[m] (tape i))⟩ := by
induction m with
| zero =>
simp only [Function.iterate_zero_apply, Function.iterate_zero, id_eq,
Function.update_eq_self]
rfl
| succ m ih =>
rw [Function.iterate_succ_apply', ih (by omega),
moveUpTo_step i k dir m (by omega)]
congr 1
funext j
by_cases hj : j = i
· subst hj
simp [Function.iterate_succ_apply']
· simp [hj]
theorem moveUpTo_spec (i : Fin tapes) (k : Nat) (dir : HeadMove)
(hk : k ≤ 12) (tape : Fin tapes → Tape) :
HaltsExactly (moveUpTo i k dir) ((moveUpTo i k dir).startCfg tape) k
true := by
have hmin : min k 12 = k := by omega
constructor
· rw [moveUpTo_run i k dir k (by omega) tape]
simp [moveUpTo, hmin]
· intro j hj
rw [moveUpTo_run i k dir j (by omega) tape]
simp [moveUpTo, hmin]
omega
theorem moveUpTo_tape (i : Fin tapes) (k : Nat) (dir : HeadMove)
(hk : k ≤ 12) (tape : Fin tapes → Tape) :
(((moveUpTo i k dir).step^[k]) ((moveUpTo i k dir).startCfg tape)).tape =
Function.update tape i ((moveDir dir)^[k] (tape i)) := by
rw [moveUpTo_run i k dir k (by omega) tape]
/-! ## The parking scan's final tapes -/
/-- `blankIndex` of a written run followed by a blank. -/
theorem blankIndex_written (W T : List TapeSymbol)
(hW : ∀ c ∈ W, c ≠ TapeSymbol.blank) :
blankIndex (W ++ TapeSymbol.blank :: T) = W.length := by
induction W with
| nil => rfl
| cons c cs ih =>
cases hc : c with
| blank =>
exact absurd hc (hW c (List.mem_cons_self))
| bit b =>
simp only [List.cons_append, blankIndex, List.length_cons]
rw [ih (fun x hx => hW x (List.mem_cons_of_mem _ hx))]
/-- The tapes the parking scan leaves behind — the navigation module's
specification gives the halt but not the tapes, so this reconstructs the loop
rounds and projects. -/
theorem scanToBlank_tape_of (i : Fin tapes) (dir : HeadMove)
(tape : Fin tapes → Tape) (d : Nat)
(hlt : ∀ k, k < d →
((moveDir dir)^[k + 1] (tape i)).head ≠ TapeSymbol.blank)
(heq : ((moveDir dir)^[d + 1] (tape i)).head = TapeSymbol.blank) :
(((scanToBlank i dir).step^[d * 4 + 3])
((scanToBlank i dir).startCfg tape)).tape =
scanTapesDir tape i dir (d + 1) := by
have hround : ∀ m, m < d →
HaltsExactly (scanBody i dir)
((scanBody i dir).startCfg (scanTapesDir tape i dir m))
(1 + 1 + 1) true ∧
(scanBody i dir).startCfg (scanTapesDir tape i dir (m + 1)) =
⟨(scanBody i dir).start,
(((scanBody i dir).step^[1 + 1 + 1])
((scanBody i dir).startCfg (scanTapesDir tape i dir m))).tape⟩ := by
intro m hm
constructor
· have h := scanBody_round i dir tape m
rwa [notBlankAt_true i (scanTapesDir tape i dir (m + 1))
(by rw [scanTapesDir_head]; exact hlt m hm)] at h
· rw [scanBody_round_tape]
rfl
have hexit : HaltsExactly (scanBody i dir)
((scanBody i dir).startCfg (scanTapesDir tape i dir d)) (1 + 1 + 1)
false := by
have h := scanBody_round i dir tape d
rwa [notBlankAt_false i (scanTapesDir tape i dir (d + 1))
(by rw [scanTapesDir_head]; exact heq)] at h
have htape := TypedMachine.repeatUntilFalse_tape (scanBody i dir)
(fun m => (scanBody i dir).startCfg (scanTapesDir tape i dir m))
(fun _ => 1 + 1 + 1) d (1 + 1 + 1) hround hexit
rw [scanBody_round_tape] at htape
have hcost : loopCost (fun _ => 1 + 1 + 1) d + (1 + 1 + 1) = d * 4 + 3 := by
rw [loopCost_const]
rw [← hcost]
show ((((scanBody i dir).repeatUntilFalse).step^[
loopCost (fun _ => 1 + 1 + 1) d + (1 + 1 + 1)])
((scanToBlank i dir).startCfg tape)).tape = _
have hcfg0 : (scanToBlank i dir).startCfg tape =
(scanBody i dir).startCfg (scanTapesDir tape i dir 0) := by
rw [scanTapesDir_zero]
rfl
rw [hcfg0]
exact htape
end SipserGacsLautemann