Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Composing initialisation with the loop

Definition
sgl_merge_compose

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Composing initialisation with the loop, plus the bookkeeping the final theorem needs.

mergeComposite writes the initial region and then simulates; mergeComposite_spec says that from physical tapes matching the virtual ones below the host, with the host and both hosted virtual tapes empty, it halts with the simulated machine's answer in at most 15+(rounds+1)(500(1+2 rounds)+1501)15 + ({\rm rounds}+1)(500(1 + 2\,{\rm rounds}) + 1501)15+(rounds+1)(500(1+2rounds)+1501) steps.

Two anticipated obstacles turned out not to exist. The index arithmetic relating tapes+(scratch+2)\mathrm{tapes} + (\mathrm{scratch}+2)tapes+(scratch+2) to (tapes+scratch)+2(\mathrm{tapes}+\mathrm{scratch})+2(tapes+scratch)+2 needs no casts at all: Nat.add recurses on its second argument, so the two are definitionally equal and every statement typechecks across the boundary unchanged. And the composite's state type — seventeen layers of sums and products over an Option of a function type — has a Fintype instance by ordinary synthesis, once Option's instance is in scope. The toMachine bridge then applies with no bespoke encoding.

Also here: running a machine is iterating its step; a halted machine stays put; and scratch padding does not change totalInputLength, so the two scratch-paddings of an input give the same time bound.

Definition code
import Definitions.Def_sgl_merge_init
import Definitions.Def_sgl_polynomial_closures
import Mathlib.Data.Fintype.Option
import Mathlib.Data.Fintype.Sum
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.Fintype.Pi

/-!
# Composing initialisation with the loop

Module F3 of DESIGN_step_spec_endgame, first part: the machine that writes the
initial region and then runs the simulation, together with the small facts the
final theorem needs about inputs and running times.

Two things anticipated as friction turned out not to be.  The index arithmetic
relating `tapes + (scratch + 2)` to `(tapes + scratch) + 2` needs no casts —
`Nat.add` recurses on its second argument, so the two are *definitionally*
equal.  And the composite's state type, deep as it is, has a `Fintype`
instance by synthesis once `Option`'s is in scope.
-/

namespace SipserGacsLautemann

set_option synthInstance.maxSize 4000
set_option synthInstance.maxHeartbeats 2000000

variable {states : Nat}

/-! ## Running a machine is iterating its step -/

theorem Machine.run_eq_iterate {n : Nat} (M : Machine n states)
    (input : Fin n → List Bool) (t : Nat) :
    M.run input t = (M.step^[t]) (initialConfiguration M input) := by
  induction t with
  | zero => rfl
  | succ t ih => rw [Machine.run, ih, Function.iterate_succ_apply']

/-- A halted machine stays where it is. -/
theorem Machine.step_of_halted {n : Nat} (M : Machine n states)
    (c : Configuration n states) (h : (M.result c.state).isSome) :
    M.step c = c := by
  unfold Machine.step
  cases hr : M.result c.state with
  | none => rw [hr] at h; simp at h
  | some b => rfl

/-! ## Scratch padding does not change the input length -/

theorem totalInputLength_withScratch {tapes : Nat} (scratch : Nat)
    (input : Fin tapes → List Bool) :
    totalInputLength (withScratch scratch input) = totalInputLength input := by
  classical
  unfold totalInputLength
  rw [List.sum_ofFn, List.sum_ofFn, Fin.sum_univ_add]
  have hleft : ∀ i : Fin tapes,
      ((withScratch scratch input) (Fin.castAdd scratch i)).length =
        (input i).length := by
    intro i
    have hlt : (Fin.castAdd scratch i).val < tapes := i.isLt
    simp [withScratch, hlt]
  have hright : ∀ i : Fin scratch,
      ((withScratch scratch input) (Fin.natAdd tapes i)).length = 0 := by
    intro i
    have hge : ¬ ((Fin.natAdd tapes i).val < tapes) := by simp
    simp [withScratch, hge]
  rw [Finset.sum_congr rfl (fun i _ => hleft i),
    Finset.sum_congr rfl (fun i _ => hright i)]
  simp

/-- The two scratch paddings of the same input agree wherever both are
defined, so the physical and virtual tapes coincide below the host. -/
theorem withScratch_agree {tapes : Nat} (scratch : Nat)
    (input : Fin tapes → List Bool) (j : Nat) (hj : j < tapes + scratch) :
    withScratch (scratch + 1) input ⟨j, by omega⟩ =
      withScratch (scratch + 2) input ⟨j, by omega⟩ := by
  by_cases h : j < tapes <;> simp [withScratch, h]

/-! ## The composite machine -/

/-- Write the initial region, then simulate. -/
noncomputable def mergeComposite (tapes' : Nat)
    (M : Machine (tapes' + 2) states) (q₀ : Fin states) :=
  (initRegion (Fin.last tapes')).andThen fun _ =>
    mergeMachine tapes' M q₀

/-- **The composite decides what the simulated machine decides.**  Given the
physical tapes (host empty) matching the virtual ones below the host, and the
two hosted virtual tapes empty, the composite halts with the simulated
machine's answer. -/
theorem mergeComposite_spec {tapes' : Nat} (M : Machine (tapes' + 2) states)
    (virt : Configuration (tapes' + 2) states)
    (base : Fin (tapes' + 1) → Tape) (rounds : Nat) (ans : Bool)
    (hident : IdentPart tapes' virt base)
    (hhost : ∀ sd, virt.tape (hostIdx tapes' sd) = ⟨[], TapeSymbol.blank, []⟩)
    (hbase : base (Fin.last tapes') = ⟨[], TapeSymbol.blank, []⟩)
    (hlive : ∀ i, i ≤ rounds → M.result ((M.step^[i]) virt).state = none)
    (hhalt : M.result ((M.step^[rounds + 1]) virt).state = some ans) :
    ∃ total : Nat,
      total ≤ 15 + (rounds + 1) * (500 * (1 + 2 * rounds) + 1501) ∧
      HaltsExactly (mergeComposite tapes' M virt.state)
        ((mergeComposite tapes' M virt.state).startCfg base) total ans := by
  classical
  set R₀ := initRound M virt base hident hhost with hR₀
  obtain ⟨loopTotal, hloopBound, hloop⟩ :=
    mergeMachine_spec R₀ rounds ans (by simpa [hR₀] using hlive)
      (by simpa [hR₀] using hhalt)
  -- the initial region
  obtain ⟨hinit, hinitTape⟩ := initRegion_spec (Fin.last tapes') base hbase
  -- the loop starts where the initial region left off
  have hstart : (mergeMachine tapes' M R₀.virt.state).startCfg R₀.park =
      TypedConfiguration.inLoop R₀.virt.state
        ((stepProgram tapes' M R₀.virt.state).startCfg R₀.park) := rfl
  have hloop' : HaltsExactly (mergeMachine tapes' M virt.state)
      ((mergeMachine tapes' M virt.state).startCfg
        (Function.update base (Fin.last tapes')
          (ParkedTape [initBlock] [TapeSymbol.blank]))) loopTotal ans := by
    rw [show (Function.update base (Fin.last tapes')
        (ParkedTape [initBlock] [TapeSymbol.blank])) = R₀.park from rfl]
    exact hloop
  have hchain := chainStepC hinit hinitTape hloop'
  refine ⟨14 + 1 + loopTotal, ?_, hchain.1⟩
  have hlen : R₀.blocks.length = 1 := rfl
  rw [hlen] at hloopBound
  have hnorm : 500 * (1 + 2 * rounds) + 1500 + 1 =
      500 * (1 + 2 * rounds) + 1501 := by omega
  rw [hnorm] at hloopBound
  omega

end SipserGacsLautemann
Source
Composite machine for the two-track simulation; builds on Def_sgl_merge_init.

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