Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The dilated region hosts input and scratch

Definition
sgl_dilation_hosts

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The dilated region hosts the input beside an empty tape — the semantic payoff of the dilation, and the fact eliminate_last_scratch_tape turns on.

Both tracks split at the first block, so a single SplitAtFlag serves both. Track A then projects to the input followed by one blank — PadEq to the input tape, the trailing blank being exactly the padding PadEq was designed to absorb. Track B projects to blanks throughout — PadEq to the empty tape.

hostsPair_encodeInputBlocks states it for every input, the empty case falling to the merge-initial block. So after dilation the physical host tape carries, as two interleaved tracks, precisely the last input tape and the scratch tape the simulated machine expects — which is what lets the merge stack run unchanged over an input-bearing host.

Definition code
import Definitions.Def_sgl_dilation_spec

/-!
# The dilated region hosts the input beside an empty tape

Module G3: the semantic payoff of the dilation.  Both tracks split at the
first block, so one split serves both; track A then projects to the input
followed by a single blank, and track B to blanks throughout — each `PadEq` to
the virtual tape it must carry.
-/

namespace SipserGacsLautemann

/-- **A dilated non-empty input is hosted correctly.** -/
theorem hostsPair_dilBlocks (x : Bool) (xs : List Bool) :
    HostsPair (dilBlocks (x :: xs))
      (fun sd => match sd with
        | TrackSide.A => Tape.ofBits (x :: xs)
        | TrackSide.B => ⟨[], TapeSymbol.blank, []⟩) := by
  intro side
  refine ⟨[], inputBlock x true,
    (xs.map fun c => inputBlock c false) ++ [exitBlock],
    dilBlocks_split side x xs, ?_⟩
  cases side with
  | A =>
      refine ⟨[], [TapeSymbol.blank], AllBlank.nil, AllBlank.single, ?_⟩
      show trackOfSplit TrackSide.A.pick [] (inputBlock x true) _ = _
      rw [trackOfSplit, trackTape]
      simp [trackSyms, TrackSide.pick, inputBlock, exitBlock, Tape.ofBits,
        bitCells]
  | B =>
      refine ⟨[], List.replicate (xs.length + 1) TapeSymbol.blank,
        AllBlank.nil, ?_, ?_⟩
      · intro c hc
        exact List.eq_of_mem_replicate hc
      · show trackOfSplit TrackSide.B.pick [] (inputBlock x true) _ = _
        rw [trackOfSplit, trackTape]
        simp [trackSyms, TrackSide.pick, inputBlock, exitBlock]
        induction xs with
        | nil => rfl
        | cons y ys ih => simp [List.replicate_succ, inputBlock, ih]

/-- **The general statement**: the region `encodeInputBlocks xs` hosts the
input tape beside the empty tape, for every input. -/
theorem hostsPair_encodeInputBlocks (xs : List Bool) :
    HostsPair (encodeInputBlocks xs)
      (fun sd => match sd with
        | TrackSide.A => Tape.ofBits xs
        | TrackSide.B => ⟨[], TapeSymbol.blank, []⟩) := by
  cases xs with
  | nil =>
      refine hostsPair_initBlock _ ?_
      intro sd
      cases sd <;> rfl
  | cons x xs' =>
      have h := hostsPair_dilBlocks x xs'
      rw [encodeInputBlocks_cons, dilSuffix_nonempty_eq]
      exact h

end SipserGacsLautemann
Source
Hosting correctness for the dilated region; builds on Def_sgl_dilation_spec.

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