Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The dilation round

Definition
sgl_dilation_body

by Henry Yuen · Jul 26, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-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 15∣rest∣+4815|{\rm rest}|+4815∣rest∣+48 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.

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