Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The dilation pre-pass

Definition
sgl_dilation_pre

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The pre-pass: from the raw input tape to the first round's layout.

One left step materialises the home blank; one right step returns to position zero; the whole input is then shifted five right by the same primitive the rounds use, which simultaneously opens the first five-blank separator and leaves the head on home; a final right step lands on the separator start. prePass_spec: cost at most 15∣rest∣+4015|{\rm rest}|+4015∣rest∣+40, ending exactly on the round invariant with no blocks written — which is what the loop consumes.

This is where the design collapse recorded earlier pays off: the planned shift-by-one pre-pass machine, with its own cycle and correctness proofs, was never needed. Shifting by five with the existing shifter does both jobs at once.

Definition code
import Definitions.Def_sgl_dilation_loop

/-!
# The pre-pass

Module G2's last machine: from the raw input tape to the first round's layout.

One left step materialises the home blank; one right step returns to position
zero; then the whole input is shifted five right by the same primitive the
rounds use, which both creates the first five-blank separator and leaves the
head on home; a final right step lands on the separator start.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

theorem ofBits_eq_cellsTape (xs : List Bool) :
    Tape.ofBits xs = cellsTape [] (bitCells xs) := by
  cases xs with
  | nil => rfl
  | cons x xs' => rfl

set_option maxHeartbeats 1000000 in
/-- Home, then position zero. -/
theorem prePass_enter (i : Fin tapes) (xs : List Bool) (G : List TapeSymbol)
    (T : Fin tapes → Tape)
    (hT : T i = cellsTape [] (bitCells xs ++ G)) :
    ((moveDir HeadMove.right) ((moveDir HeadMove.left) (T i))) =
      cellsTape [TapeSymbol.blank] (bitCells xs ++ G) := by
  rw [hT]
  cases h : bitCells xs ++ G with
  | nil =>
      show moveDir HeadMove.right (moveDir HeadMove.left
        (cellsTape [] [])) = _
      rfl
  | cons c R =>
      show moveDir HeadMove.right (moveDir HeadMove.left
        (cellsTape [] (c :: R))) = _
      rw [show moveDir HeadMove.left (cellsTape [] (c :: R)) =
        cellsTape [] (TapeSymbol.blank :: c :: R) from rfl]
      rw [cellsTape_moveRight]


set_option maxHeartbeats 4000000 in
/-- **The pre-pass on a non-empty input.**  Five blanks are opened before the
input and the head lands on the first separator: the round invariant with no
blocks written. -/
theorem prePass_spec (i : Fin tapes) (x : Bool) (rest : List Bool)
    (G : List TapeSymbol) (T : Fin tapes → Tape) (hG : AllBlank G)
    (hT : T i = cellsTape [] (bitCells (x :: rest) ++ G)) :
    ∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
      cost ≤ 15 * rest.length + 40 ∧
      HaltsExactly (prePass i) ((prePass i).startCfg T) cost true ∧
      (((prePass i).step^[cost]) ((prePass i).startCfg T)).tape =
        Function.update T i (dilTape [] (x :: rest) G') := by
  classical
  -- A: one left
  have hA := moveUpTo_spec i 1 HeadMove.left (by omega) T
  set T1 := Function.update T i ((moveDir HeadMove.left) (T i)) with hT1
  have hAt : (((moveUpTo i 1 HeadMove.left).step^[1])
      ((moveUpTo i 1 HeadMove.left).startCfg T)).tape = T1 := by
    rw [moveUpTo_tape i 1 HeadMove.left (by omega) T, hT1]
    rfl
  -- B: one right, back to position zero
  have hB := moveUpTo_spec i 1 HeadMove.right (by omega) T1
  set T2 := Function.update T i
    (cellsTape [TapeSymbol.blank] (bitCells (x :: rest) ++ G)) with hT2
  have hBt : (((moveUpTo i 1 HeadMove.right).step^[1])
      ((moveUpTo i 1 HeadMove.right).startCfg T1)).tape = T2 := by
    rw [moveUpTo_tape i 1 HeadMove.right (by omega) T1, hT2, hT1]
    simp only [Function.update_idem, Function.update_self]
    congr 1
    rw [Function.iterate_one]
    exact prePass_enter i (x :: rest) G T hT
  have hT2i : T2 i =
      cellsTape [TapeSymbol.blank] (bitCells (x :: rest) ++ G) := by
    rw [hT2]; simp
  -- C: scan right to the end of the input
  set d := rest.length with hd
  have hadv : ∀ k, k ≤ d →
      ((moveDir HeadMove.right)^[k + 1]) (T2 i) =
        cellsTape ((bitCells ((x :: rest).take (k + 1))).reverse ++
          [TapeSymbol.blank]) (bitCells ((x :: rest).drop (k + 1)) ++ G) := by
    intro k hk
    rw [hT2i]
    have hsplit : bitCells (x :: rest) ++ G =
        bitCells ((x :: rest).take (k + 1)) ++
          (bitCells ((x :: rest).drop (k + 1)) ++ G) := by
      rw [← List.append_assoc, ← bitCells_append, List.take_append_drop]
    have hlen : (bitCells ((x :: rest).take (k + 1))).length = k + 1 := by
      simp [bitCells, List.length_take]
      omega
    rw [hsplit]
    have hc := cellsTape_advance (bitCells ((x :: rest).take (k + 1)))
      [TapeSymbol.blank] (bitCells ((x :: rest).drop (k + 1)) ++ G)
    rw [hlen] at hc
    exact hc
  have hlt : ∀ k, k < d →
      (((moveDir HeadMove.right)^[k + 1]) (T2 i)).head ≠ TapeSymbol.blank := by
    intro k hk
    rw [hadv k (by omega)]
    obtain ⟨y, ys, hdrop⟩ : ∃ y ys, (x :: rest).drop (k + 1) = y :: ys := by
      cases hdk : (x :: rest).drop (k + 1) with
      | nil =>
          exfalso
          have := congrArg List.length hdk
          simp [List.length_drop] at this
          omega
      | cons y ys => exact ⟨y, ys, rfl⟩
    rw [hdrop]
    simp [cellsTape]
  have heq : (((moveDir HeadMove.right)^[d + 1]) (T2 i)).head =
      TapeSymbol.blank := by
    rw [hadv d le_rfl]
    rw [show (x :: rest).drop (d + 1) = [] by
      rw [hd]; simp]
    exact cellsTape_head_allBlank _ G hG
  have hC := scanToBlank_spec_of i HeadMove.right T2 d hlt heq
  have hCt := scanToBlank_tape_of i HeadMove.right T2 d hlt heq
  set T3 := Function.update T2 i
    (cellsTape ((bitCells (x :: rest)).reverse ++ [TapeSymbol.blank]) G)
    with hT3
  have hCt' : (((scanToBlank i HeadMove.right).step^[d * 4 + 3])
      ((scanToBlank i HeadMove.right).startCfg T2)).tape = T3 := by
    rw [hCt, hT3]
    show scanTapesDir T2 i HeadMove.right (d + 1) = _
    rw [scanTapesDir]
    congr 1
    rw [hadv d le_rfl]
    rw [show (x :: rest).drop (d + 1) = [] by rw [hd]; simp,
      show (x :: rest).take (d + 1) = x :: rest by rw [hd]; simp]
    simp
  have hT3i : T3 i =
      cellsTape ((bitCells (x :: rest)).reverse ++ [TapeSymbol.blank]) G := by
    rw [hT3]; simp
  -- D: one left, onto the last input cell
  have hbc : (bitCells (x :: rest)).reverse =
      (bitCells (x :: rest)).reverse := rfl
  obtain ⟨lc, Lr, hLr⟩ : ∃ lc Lr,
      (bitCells (x :: rest)).reverse = lc :: Lr := by
    cases hrv : (bitCells (x :: rest)).reverse with
    | nil =>
        exfalso
        have := congrArg List.length hrv
        simp [bitCells] at this
    | cons a t => exact ⟨a, t, rfl⟩
  obtain ⟨G₂, hG₂, hmv⟩ := moveDir_left_allBlank lc (Lr ++ [TapeSymbol.blank])
    G hG
  have hD := moveUpTo_spec i 1 HeadMove.left (by omega) T3
  set T4 := Function.update T3 i
    (cellsTape (Lr ++ [TapeSymbol.blank]) (lc :: G₂)) with hT4
  have hDt : (((moveUpTo i 1 HeadMove.left).step^[1])
      ((moveUpTo i 1 HeadMove.left).startCfg T3)).tape = T4 := by
    rw [moveUpTo_tape i 1 HeadMove.left (by omega) T3, hT4]
    congr 1
    rw [Function.iterate_one, hT3i, hLr]
    show moveDir HeadMove.left
      (cellsTape (lc :: (Lr ++ [TapeSymbol.blank])) G) = _
    rw [hmv]
  have hT4i : T4 i = cellsTape (Lr ++ [TapeSymbol.blank]) (lc :: G₂) := by
    rw [hT4]; simp
  -- E,F: the probe
  obtain ⟨cc, Lr2, hcL⟩ : ∃ cc Lr2, Lr ++ [TapeSymbol.blank] = cc :: Lr2 := by
    cases hL : Lr with
    | nil => exact ⟨TapeSymbol.blank, [], by simp⟩
    | cons a t => exact ⟨a, t ++ [TapeSymbol.blank], by simp⟩
  have hE := moveUpTo_spec i 5 HeadMove.right (by omega) T4
  set T5 := Function.update T4 i
    ((moveDir HeadMove.right)^[5] (T4 i)) with hT5
  have hEt : (((moveUpTo i 5 HeadMove.right).step^[5])
      ((moveUpTo i 5 HeadMove.right).startCfg T4)).tape = T5 := by
    rw [moveUpTo_tape i 5 HeadMove.right (by omega) T4, hT5]
  have hF := moveUpTo_spec i 5 HeadMove.left (by omega) T5
  set T6 := Function.update T5 i
    (cellsTape (Lr ++ [TapeSymbol.blank])
      (lc :: List.replicate 5 TapeSymbol.blank ++ G₂.drop 5)) with hT6
  have hFt : (((moveUpTo i 5 HeadMove.left).step^[5])
      ((moveUpTo i 5 HeadMove.left).startCfg T5)).tape = T6 := by
    rw [moveUpTo_tape i 5 HeadMove.left (by omega) T5, hT6, hT5]
    simp only [Function.update_idem, Function.update_self]
    congr 1
    rw [hT4i, hcL]
    exact moveDir_probe5 cc lc Lr2 G₂ hG₂
  have hT6i : T6 i = cellsTape (Lr ++ [TapeSymbol.blank])
      (lc :: List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
    rw [hT6]; simp
  -- G: the shift
  have hT6i' : T6 i = cellsTape (Lr ++ TapeSymbol.blank :: [])
      (lc :: List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
    rw [hT6i]
  have hLrnb : ∀ c ∈ Lr, c ≠ TapeSymbol.blank := by
    intro c hc
    have : c ∈ (bitCells (x :: rest)).reverse := by
      rw [hLr]; exact List.mem_cons_of_mem _ hc
    exact bitCells_ne_blank _ c (List.mem_reverse.mp this)
  have hlcnb : lc ≠ TapeSymbol.blank := by
    have : lc ∈ (bitCells (x :: rest)).reverse := by rw [hLr]; simp
    exact bitCells_ne_blank _ lc (List.mem_reverse.mp this)
  obtain ⟨hGh, hGt⟩ := shiftSeg5_spec i Lr lc [] (G₂.drop 5) T6
    hlcnb hLrnb hT6i'
  set T7 := Function.update T6 i
    (cellsTape [] (TapeSymbol.blank ::
      List.replicate 5 TapeSymbol.blank ++ (Lr.reverse ++ lc :: G₂.drop 5)))
    with hT7
  have hGt' : (((shiftSeg5 i).step^[11 * (Lr.length + 1) + 1])
      ((shiftSeg5 i).startCfg T6)).tape = T7 := by
    rw [hGt, hT7]
  have hrev : Lr.reverse ++ lc :: G₂.drop 5 =
      bitCells (x :: rest) ++ G₂.drop 5 := by
    have h1 : (lc :: Lr).reverse = bitCells (x :: rest) := by
      rw [← hLr, List.reverse_reverse]
    have h2 : (lc :: Lr).reverse = Lr.reverse ++ [lc] := by simp
    rw [← h1, h2, List.append_assoc]
    rfl
  have hT7i : T7 i = cellsTape [] (TapeSymbol.blank ::
      List.replicate 5 TapeSymbol.blank ++
        (bitCells (x :: rest) ++ G₂.drop 5)) := by
    rw [hT7]
    simp only [Function.update_self]
    rw [hrev]
  -- H: one right, onto the separator start
  have hH := moveUpTo_spec i 1 HeadMove.right (by omega) T7
  set T8 := Function.update T7 i
    (cellsTape [TapeSymbol.blank] (List.replicate 5 TapeSymbol.blank ++
      (bitCells (x :: rest) ++ G₂.drop 5))) with hT8
  have hHt : (((moveUpTo i 1 HeadMove.right).step^[1])
      ((moveUpTo i 1 HeadMove.right).startCfg T7)).tape = T8 := by
    rw [moveUpTo_tape i 1 HeadMove.right (by omega) T7, hT8]
    congr 1
    rw [Function.iterate_one, hT7i]
    exact cellsTape_moveRight [] TapeSymbol.blank _
  -- assemble
  have c7 := chainStepC hGh hGt' hH
  have c6 := chainStepC hF hFt c7.1
  have c5 := chainStepC hE hEt c6.1
  have c4 := chainStepC hD hDt c5.1
  have c3 := chainStepC hC hCt' c4.1
  have c2 := chainStepC hB hBt c3.1
  have c1 := chainStepC hA hAt c2.1
  refine ⟨1 + 1 + (1 + 1 + (d * 4 + 3 + 1 + (1 + 1 + (5 + 1 + (5 + 1 +
    ((11 * (Lr.length + 1) + 1) + 1 + 1)))))), G₂.drop 5, hG₂.drop 5,
    ?_, c1.1, ?_⟩
  · have hLrlen : Lr.length = rest.length := by
      have := congrArg List.length hLr
      simp [bitCells] at this
      omega
    rw [hLrlen, hd]
    omega
  · have hfin := c1.2
    rw [c2.2] at hfin
    rw [c3.2] at hfin
    rw [c4.2] at hfin
    rw [c5.2] at hfin
    rw [c6.2] at hfin
    rw [c7.2] at hfin
    have hfin' : ((prePass i).step^[1 + 1 + (1 + 1 + (d * 4 + 3 + 1 +
        (1 + 1 + (5 + 1 + (5 + 1 +
          ((11 * (Lr.length + 1) + 1) + 1 + 1))))))])
        ((prePass i).startCfg T) = _ := hfin
    rw [hfin']
    show (((moveUpTo i 1 HeadMove.right).step^[1])
      ((moveUpTo i 1 HeadMove.right).startCfg T7)).tape = _
    rw [hHt, hT8, hT7, hT6, hT5, hT4, hT3, hT2]
    simp only [Function.update_idem]
    rw [dilTape]
    congr 1

end SipserGacsLautemann
Source
Pre-pass for in-place dilation; builds on Def_sgl_dilation_loop.

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