Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The exit round's chain

Definition
sgl_dilation_exit

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The post-read chain when the read finds blank: the same seven stages as a bit round, with the shifter halting at once, writing the round's block for the captured blank. Split out for verification size — the platform verifier budgets per request, and these junction proofs are individually expensive.

Definition code
import Definitions.Def_sgl_dilation_core

/-!
# The exit round's chain

The post-read chain when the read finds blank: the same seven stages as a
bit round, with the shifter halting at once, writing the round's block for the
captured blank.

Split out for verification size — the platform verifier budgets per request,
and these junction proofs are individually expensive.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

set_option maxHeartbeats 4000000 in
/-- **The post-read chain on a blank**: the exit round.  Same chain, the
shifter halting at once, writing the round's block for the captured blank. -/
theorem dilCont_spec_blank (i : Fin tapes) (first : Bool)
    (done : List Block) (G : List TapeSymbol)
    (T2 : Fin tapes → Tape) (hG : AllBlank G)
    (hT2 : T2 i = cellsTape
      (List.replicate 5 TapeSymbol.blank ++
        ((encodeBlocks done).reverse ++ [TapeSymbol.blank]))
      (TapeSymbol.blank :: G)) :
    ∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
      cost ≤ 40 ∧
      HaltsExactly (dilCont i (some TapeSymbol.blank) first)
        ((dilCont i (some TapeSymbol.blank) first).startCfg T2) cost true ∧
      (((dilCont i (some TapeSymbol.blank) first).step^[cost])
        ((dilCont i (some TapeSymbol.blank) first).startCfg T2)).tape =
        Function.update T2 i (cellsTape
          ((encodeBlocks (done ++
            [blockFor (some TapeSymbol.blank) first])).reverse ++
            [TapeSymbol.blank])
          (List.replicate 5 TapeSymbol.blank ++ G')) := by
  classical
  set L0 := (encodeBlocks done).reverse ++ [TapeSymbol.blank] with hL0
  set L2 := List.replicate 5 TapeSymbol.blank ++ L0 with hL2
  set rest : List Bool := [] with hrest
  set d := rest.length with hd
  have hT2' : T2 i = cellsTape L2 (TapeSymbol.blank :: bitCells rest ++ G) := by
    rw [hT2, hrest]
    rfl
  -- stage C, as in the bit case
  have hadv : ∀ k, k ≤ d →
      ((moveDir HeadMove.right)^[k + 1]) (T2 i) =
        cellsTape ((TapeSymbol.blank :: bitCells (rest.take k)).reverse ++ L2)
          (bitCells (rest.drop k) ++ G) := by
    intro k hk
    have hk0 : k = 0 := by
      rw [hd, hrest] at hk
      simpa using hk
    subst hk0
    simp only [Nat.zero_add]
    rw [hT2']
    rw [show TapeSymbol.blank :: bitCells rest ++ G =
      (TapeSymbol.blank :: bitCells (rest.take 0)) ++
        (bitCells (rest.drop 0) ++ G) by simp [hrest]]
    rw [show (1 : Nat) =
      (TapeSymbol.blank :: bitCells (rest.take 0)).length by simp [hrest]]
    rw [cellsTape_advance]
  have hlt : ∀ k, k < d →
      (((moveDir HeadMove.right)^[k + 1]) (T2 i)).head ≠ TapeSymbol.blank := by
    intro k hk
    exfalso
    rw [hd, hrest] at hk
    simp at hk
  have heq : (((moveDir HeadMove.right)^[d + 1]) (T2 i)).head =
      TapeSymbol.blank := by
    rw [hadv d le_rfl]
    rw [show rest.drop d = [] by rw [hd]; exact List.drop_length]
    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 rest).reverse ++ [TapeSymbol.blank] ++ L2) 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 rest.drop d = [] by rw [hd]; exact List.drop_length,
      show rest.take d = rest by rw [hd]; exact List.take_length]
    simp
  have hT3i : T3 i =
      cellsTape ((bitCells rest).reverse ++ [TapeSymbol.blank] ++ L2) G := by
    rw [hT3]; simp
  have hrest' : rest = [] := hrest
  -- ----- D: one left -----
  obtain ⟨G₂, hG₂, hmv⟩ := moveDir_left_allBlank TapeSymbol.blank L2 G hG
  have hD := moveUpTo_spec i 1 HeadMove.left (by omega) T3
  set T4 := Function.update T3 i (cellsTape L2 (TapeSymbol.blank :: 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]
    show moveDir HeadMove.left
      (cellsTape (TapeSymbol.blank :: L2) G) = _
    rw [hmv]
  have hT4i : T4 i = cellsTape L2 (TapeSymbol.blank :: G₂) := by
    rw [hT4]; simp
  -- ----- E,F: the probe -----
  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 L2 (TapeSymbol.blank ::
      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, hL2]
    show ((moveDir HeadMove.left)^[5])
      (((moveDir HeadMove.right)^[5]) (cellsTape
        (TapeSymbol.blank :: (List.replicate 4 TapeSymbol.blank ++ L0))
        (TapeSymbol.blank :: G₂))) = _
    rw [moveDir_probe5 TapeSymbol.blank TapeSymbol.blank _ G₂ hG₂]
    rfl
  have hT6i : T6 i = cellsTape L2 (TapeSymbol.blank ::
      List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
    rw [hT6]; simp
  -- ----- G: the shifter halts at once -----
  obtain ⟨hGh, hGt⟩ := shiftSeg5_halt_spec i T6 (by rw [hT6i]; rfl)
  -- ----- H: five left -----
  have hH := moveUpTo_spec i 5 HeadMove.left (by omega) T6
  set T7 := Function.update T6 i
    (cellsTape L0 (List.replicate 5 TapeSymbol.blank ++ TapeSymbol.blank ::
      List.replicate 5 TapeSymbol.blank ++ G₂.drop 5)) with hT7
  have hHt : (((moveUpTo i 5 HeadMove.left).step^[5])
      ((moveUpTo i 5 HeadMove.left).startCfg T6)).tape = T7 := by
    rw [moveUpTo_tape i 5 HeadMove.left (by omega) T6, hT7]
    congr 1
    rw [hT6i, hL2]
    exact retreat5 L0 _ TapeSymbol.blank
  have hT7i : T7 i = cellsTape L0
      (List.replicate 5 TapeSymbol.blank ++ TapeSymbol.blank ::
        List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
    rw [hT7]; simp
  -- ----- I: write the block -----
  have hI := writeRun_spec i
    (Block.toCells (blockFor (some TapeSymbol.blank) first)) T7 _ _ hT7i
  have hIt := writeRun_tape i
    (Block.toCells (blockFor (some TapeSymbol.blank) first)) T7 _ _ hT7i
  -- ----- assemble -----
  have c6 := chainStepC hH hHt hI
  have c5 := chainStepC hGh hGt c6.1
  have c4 := chainStepC hF hFt c5.1
  have c4a := chainStepC hE hEt c4.1
  have c3 := chainStepC hD hDt c4a.1
  have c2 := chainStepC hC hCt' c3.1
  refine ⟨d * 4 + 3 + 1 + (1 + 1 + (5 + 1 + (5 + 1 + (1 + 1 +
    (5 + 1 + 6))))), G₂.drop 5, hG₂.drop 5, ?_, ?_, ?_⟩
  · have hd0 : d = 0 := by rw [hd]; rfl
    omega
  · exact c2.1
  · have hfin := c2.2
    rw [c3.2] at hfin
    rw [c4a.2] at hfin
    rw [c4.2] at hfin
    rw [c5.2] at hfin
    rw [c6.2] at hfin
    have hfin' : ((dilCont i (some TapeSymbol.blank) first).step^[
        d * 4 + 3 + 1 + (1 + 1 + (5 + 1 + (5 + 1 + (1 + 1 +
          (5 + 1 + 6)))))])
        ((dilCont i (some TapeSymbol.blank) first).startCfg T2) = _ :=
      hfin
    rw [hfin']
    show (((writeRun i (Block.toCells (blockFor (some TapeSymbol.blank)
        first))).step^[(Block.toCells (blockFor (some TapeSymbol.blank)
        first)).length]) ((writeRun i (Block.toCells (blockFor
        (some TapeSymbol.blank) first))).startCfg T7)).tape = _
    rw [hIt]
    rw [hT7, hT6, hT5, hT4, hT3]
    simp only [Function.update_idem]
    congr 1
    rw [show (List.replicate 5 TapeSymbol.blank ++ TapeSymbol.blank ::
        List.replicate 5 TapeSymbol.blank ++ G₂.drop 5).drop
          (Block.toCells (blockFor (some TapeSymbol.blank) first)).length =
        List.replicate 5 TapeSymbol.blank ++ G₂.drop 5 by
      rw [Block.toCells_length]
      rfl]
    rw [hL0]
    rw [show (Block.toCells (blockFor (some TapeSymbol.blank) first)).reverse ++
        ((encodeBlocks done).reverse ++ [TapeSymbol.blank]) =
      (encodeBlocks (done ++
        [blockFor (some TapeSymbol.blank) first])).reverse ++
        [TapeSymbol.blank] by
      rw [encodeBlocks_snoc, List.reverse_append]
      simp]

end SipserGacsLautemann
Source
In-place dilation for eliminate_last_scratch_tape.

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