Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The dilation loop

Definition
sgl_dilation_loop

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The loop consuming the remaining input, proved by induction over it. dilLoop_run: from any round configuration — head at the separator start, blocks so far to the left, remaining input compact to the right — the loop consumes the whole remainder and halts with every block appended, exit block last, at cost at most (∣rest∣+1)(15∣rest∣+49)(|{\rm rest}|+1)(15|{\rm rest}|+49)(∣rest∣+1)(15∣rest∣+49): quadratic in the input, as in-place dilation must be.

The induction chains rounds through the loop algebra's single-round lemmas rather than the round-indexed trajectory apparatus, which needs one small general fact: HaltsExactly.of_advance — a halting fact composes across a configuration advance whose prefix is fresh. That is the whole bridge, and it is worth having separately: any loop proved by direct induction rather than through a LoopRound family will want it.

Also here: dilSuffix, the blocks a round-sequence writes from a given remainder, and its identification with the region dilBlocks for non-empty input.

Definition code
import Definitions.Def_sgl_dilation_body

/-!
# The dilation loop

The loop consuming the remaining input, by induction over it.

`HaltsExactly.of_advance` is the small general bridge the induction needs: a
halting fact composes across a configuration advance whose prefix is fresh.
Any loop proved by direct induction rather than through a `LoopRound` family
will want it.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-! ## The loop -/

/-- Advancing a machine to a later configuration composes halting facts. -/
theorem HaltsExactly.of_advance {S : Type} {M : TypedMachine tapes S}
    {c₀ c₁ : TypedConfiguration tapes S} {k t : Nat} {v : Bool}
    (hadv : (M.step^[k]) c₀ = c₁)
    (hpre : ∀ j, j < k → M.result ((M.step^[j]) c₀).state = none)
    (h : HaltsExactly M c₁ t v) :
    HaltsExactly M c₀ (k + t) v := by
  constructor
  · rw [Nat.add_comm, Function.iterate_add_apply, hadv]
    exact h.halts
  · intro j hj
    rcases Nat.lt_or_ge j k with hlt | hge
    · exact hpre j hlt
    · obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hge
      rw [Nat.add_comm k d, Function.iterate_add_apply, hadv]
      exact h.fresh d (by omega)

/-- The blocks the loop writes from the remaining input, given the current
first-round flag. -/
def dilSuffix : List Bool → Bool → List Block
  | [], c => [blockFor (some TapeSymbol.blank) c]
  | x :: xs, c => inputBlock x c :: dilSuffix xs false

theorem dilSuffix_nonempty_eq (x : Bool) (xs : List Bool) :
    dilSuffix (x :: xs) true = dilBlocks (x :: xs) := by
  rw [dilBlocks]
  show inputBlock x true :: dilSuffix xs false = _
  congr 1
  induction xs with
  | nil => rfl
  | cons y ys ih =>
      show inputBlock y false :: dilSuffix ys false = _
      rw [ih]
      rfl

set_option maxHeartbeats 1000000 in
/-- **The dilation loop consumes the remaining input.**  From any round
configuration it halts with the remaining blocks (and the exit block)
appended, at quadratic cost. -/
theorem dilLoop_run (i : Fin tapes) :
    ∀ (xs : List Bool) (c : Bool) (done : List Block) (G : List TapeSymbol)
      (T : Fin tapes → Tape), AllBlank G → T i = dilTape done xs G →
      ∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
        cost ≤ (xs.length + 1) * (15 * xs.length + 49) ∧
        HaltsExactly (dilLoop i)
          (TypedConfiguration.inLoop c ⟨(dilBody i c).start, T⟩) cost false ∧
        ((((dilLoop i).step^[cost])
          (TypedConfiguration.inLoop c ⟨(dilBody i c).start, T⟩)).tape) =
          Function.update T i (dilTape (done ++ dilSuffix xs c) [] G') := by
  intro xs
  induction xs with
  | nil =>
      intro c done G T hG hT
      obtain ⟨cb, G', hG', hcb, hhalt, hread, htape⟩ :=
        dilBody_spec_blank i c done G T hG hT
      have hstop : (fun _ b => !(isBitO (stateRead b))) c
          (((dilBody i c).step^[cb])
            ((dilBody i c).startCfg T)).state = true := by
        simp only [hread]
        rfl
      have hmain := TypedMachine.loopState_spec_v
        (fun first => dilBody i first) (fun _ _ => false)
        (fun _ b => !(isBitO (stateRead b))) (fun _ _ => false)
        true (fun _ => c)
        (fun _ => (dilBody i c).startCfg T) (fun _ => 0) 0 cb true
        (by intro j hj; omega) hhalt hstop
      have hmain' : HaltsExactly (dilLoop i)
          (TypedConfiguration.inLoop c ⟨(dilBody i c).start, T⟩) cb false := by
        simpa [loopCost] using hmain
      refine ⟨cb, G', hG', by simp; omega, hmain', ?_⟩
      · have hiter := TypedMachine.loopState_iterate_body
          (fun first => dilBody i first) (fun _ _ => false)
          (fun _ b => !(isBitO (stateRead b))) (fun _ _ => false)
          true c ((dilBody i c).startCfg T) cb hhalt.fresh
        show (((dilLoop i).step^[cb])
          (TypedConfiguration.inLoop c ((dilBody i c).startCfg T))).tape = _
        rw [dilLoop, hiter]
        show (((dilBody i c).step^[cb]) ((dilBody i c).startCfg T)).tape = _
        rw [htape]
        rfl
  | cons x rest ih =>
      intro c done G T hG hT
      obtain ⟨cb, G', hG', hcb, hhalt, hread, htape⟩ :=
        dilBody_spec_bit i c x done rest G T hG hT
      have hkeep : (fun _ b => !(isBitO (stateRead b))) c
          (((dilBody i c).step^[cb])
            ((dilBody i c).startCfg T)).state = false := by
        simp only [hread]
        rfl
      set T' := Function.update T i
        (dilTape (done ++ [inputBlock x c]) rest G') with hT'
      have hT'i : T' i = dilTape (done ++ [inputBlock x c]) rest G' := by
        rw [hT']; simp
      obtain ⟨ct, G'', hG'', hct, hhalt', htape'⟩ :=
        ih false (done ++ [inputBlock x c]) G' T' hG' hT'i
      -- one round advances the loop
      have hround := TypedMachine.loopState_round
        (fun first => dilBody i first) (fun _ _ => false)
        (fun _ b => !(isBitO (stateRead b))) (fun _ _ => false)
        true (fun n => if n = 0 then c else false)
        (fun n => if n = 0 then (dilBody i c).startCfg T
          else (dilBody i false).startCfg T')
        (fun _ => cb) 0
        ⟨⟨true, by simpa using hhalt⟩, by simpa using hkeep, by simp,
          by
            simp only [if_pos rfl, if_neg (Nat.zero_ne_one ∘ Eq.symm)]
            show ((dilBody i false).startCfg T' :
                TypedConfiguration tapes _) =
              ⟨(dilBody i false).start,
                (((dilBody i c).step^[cb]) ((dilBody i c).startCfg T)).tape⟩
            rw [htape]
            rfl⟩
      have hfresh := TypedMachine.loopState_round_fresh
        (fun first => dilBody i first) (fun _ _ => false)
        (fun _ b => !(isBitO (stateRead b))) (fun _ _ => false)
        true c ((dilBody i c).startCfg T) cb true hhalt hkeep
      have hadv : ((dilLoop i).step^[cb + 1])
          (TypedConfiguration.inLoop c ⟨(dilBody i c).start, T⟩) =
          TypedConfiguration.inLoop false ⟨(dilBody i false).start, T'⟩ := by
        have := hround
        simpa using this
      refine ⟨cb + 1 + ct, G'', hG'', ?_, ?_, ?_⟩
      · have h1 : cb + 1 ≤ 15 * rest.length + 49 := by omega
        have h2 : ct ≤ (rest.length + 1) * (15 * rest.length + 49) := hct
        have h3 : (rest.length + 1) * (15 * rest.length + 49) ≤
            (rest.length + 1) * (15 * (rest.length + 1) + 49) :=
          Nat.mul_le_mul_left _ (by omega)
        have h4 : ((x :: rest).length + 1) * (15 * (x :: rest).length + 49) =
            (rest.length + 2) * (15 * (rest.length + 1) + 49) := by
          simp [List.length_cons]
        rw [h4]
        have h5 : (rest.length + 2) * (15 * (rest.length + 1) + 49) =
            (rest.length + 1) * (15 * (rest.length + 1) + 49) +
              (15 * (rest.length + 1) + 49) := by
          rw [Nat.succ_mul]
        omega
      · exact HaltsExactly.of_advance hadv
          (fun j hj => hfresh j hj) hhalt'
      · rw [show cb + 1 + ct = ct + (cb + 1) by omega,
          Function.iterate_add_apply, hadv, htape', hT']
        simp only [Function.update_idem]
        rw [show done ++ dilSuffix (x :: rest) c =
          (done ++ [inputBlock x c]) ++ dilSuffix rest false by
            rw [List.append_assoc]
            rfl]

end SipserGacsLautemann
Source
Loop correctness for in-place dilation; builds on Def_sgl_dilation_body.

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