Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_input_prep

Definition

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

Definition code
import Definitions.Def_sgl_clock_setup

/-!
# Making an input tape's shape explicit

A raw input tape is `Tape.ofBits`, whose right half is exactly the input's
cells and nothing more.  Every lemma in the round instead wants
`cellsTape (blank :: Ls) (x ++ blank :: Rs)` — the terminating blank named in
the list.  The two describe the *same* tape: positions past the written region
are blank either way, and a head that walks off the end materialises one.  Only
the representation differs.

Walking to the end and back is what converts one into the other, and the input
can guide its own walk: a guided walk stops when its guide reads a blank, which
is exactly the cell past the input.  Choosing `stay` for the worker's direction
makes the walk a pure measurement — nothing else on the tape space moves.

This is the same manoeuvre as the dilation's probe, which normalised a blank
context to explicit cells for the same reason.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-- Standing still is the identity, however long you do it. -/
theorem moveDir_stay_iterate (m : Nat) (tp : Tape) :
    ((moveDir HeadMove.stay)^[m]) tp = tp := by
  induction m with
  | zero => rfl
  | succ m ih => rw [Function.iterate_succ_apply', ih]; rfl

/-- Walk an input to its end and back, touching nothing else. -/
def normalizeInput (s w : Fin tapes) :=
  (guidedWalk s w HeadMove.stay none).andThen fun _ =>
    rewindRun s

set_option maxHeartbeats 4000000 in
/-- **The input's shape, made explicit.**  The head returns to the input's
first cell with the terminating blank now named in the representation. -/
theorem normalizeInput_spec (s w : Fin tapes) (hsw : s ≠ w)
    (x : List TapeSymbol) (T : Fin tapes → Tape)
    (hnb : ∀ c ∈ x, c ≠ TapeSymbol.blank)
    (hs : T s = cellsTape [TapeSymbol.blank] x) :
    ∃ cost : Nat,
      HaltsExactly (normalizeInput s w)
        ((normalizeInput s w).startCfg T) cost true ∧
      (((normalizeInput s w).step^[cost])
        ((normalizeInput s w).startCfg T)).tape =
        Function.update T s
          (cellsTape [TapeSymbol.blank] (x ++ [TapeSymbol.blank])) := by
  classical
  obtain ⟨hia, hib⟩ := guidedStep_move_iterate s w hsw HeadMove.stay x T
    [TapeSymbol.blank] [] (by rw [hs]; simp)
  obtain ⟨hW, hWt⟩ := guidedWalk_spec s w hsw HeadMove.stay none x.length T
    (guidedStep_move_marks s w hsw HeadMove.stay x T [TapeSymbol.blank] []
      hnb (by rw [hs]; simp))
    (by rw [hia]; rfl)
  set T1 := ((guidedStep s w HeadMove.stay none)^[x.length]) T with hT1
  have hT1s : T1 s = cellsTape (x.reverse ++ TapeSymbol.blank :: [])
      (TapeSymbol.blank :: []) := by
    rw [hia]
    rfl
  obtain ⟨hR, hRt⟩ := rewindRun_spec s x [] [] TapeSymbol.blank T1 hnb hT1s
  have hch := chainStepC hW hWt hR
  refine ⟨_, hch.1, ?_⟩
  have hfin : ((normalizeInput s w).step^[_])
      ((normalizeInput s w).startCfg T) = _ := hch.2
  rw [hfin]
  show (((rewindRun s).step^[_]) ((rewindRun s).startCfg T1)).tape = _
  rw [hRt]
  funext j
  by_cases hj : j = s
  · subst hj
    rw [Function.update_self, Function.update_self]
  · rw [Function.update_of_ne hj, Function.update_of_ne hj]
    by_cases hj2 : j = w
    · rw [hj2]
      exact hib.trans (moveDir_stay_iterate x.length (T w))
    · rw [hT1, guidedStep_other s w HeadMove.stay none x.length T j hj hj2]

end SipserGacsLautemann

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