Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Patch runs and bounded movement

Definition
sgl_patch_run

by Henry Yuen · Jul 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Patch 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 norm(c)\mathrm{norm}(c)norm(c) — 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 Fin 7\mathrm{Fin}\ 7Fin 7, 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 Fin 13\mathrm{Fin}\ 13Fin 13. 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.

Definition code
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
Source
Standard track-surgery simulation for multitape Turing machines, specialized to the model of Def_sipser_gacs_lautemann; builds on Def_sgl_region_update.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me