Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_clock_setup

Definition

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

Definition code
import Definitions.Def_sgl_guide_setup

/-!
# Setting the clock up

The clock must start long enough that its reach `2A` already covers the longest
input and the round count — after that the loop's own arithmetic keeps it ahead
forever.  `Σ|xs| + 2` marks suffice, and they are written by tallying each input
in turn onto the same tape.

`markBack` cannot do the tallying, because it rewinds its *target* as well as
its source, and a rewind walks back over every mark it finds — so a second
tally would return to the first run's start rather than its own.  Splitting the
rewinds apart fixes it: `tallyOnto` rewinds only the source, leaving the clock's
head exactly where the next run should begin.  Three tallies then concatenate
by themselves, since consecutive runs of the same symbol are one run.

The two extra marks are written first rather than last, because the clock's
left context is unconstrained but its head must end past every mark.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-- Write a mark and advance. -/
def writeMark (i : Fin tapes) :=
  TypedMachine.act (fun symbols j =>
    if j = i then (TapeSymbol.bit true, HeadMove.right)
    else (symbols j, HeadMove.stay))

theorem writeMark_spec (i : Fin tapes) (L R : List TapeSymbol)
    (T : Fin tapes → Tape) (hT : T i = cellsTape L R) :
    HaltsExactly (writeMark i) ((writeMark i).startCfg T) 1 true ∧
    (((writeMark i).step^[1]) ((writeMark i).startCfg T)).tape =
      Function.update T i (cellsTape (TapeSymbol.bit true :: L) R.tail) := by
  classical
  refine ⟨TypedMachine.act_spec
    (fun symbols : Fin tapes → TapeSymbol => fun j =>
      if j = i then (TapeSymbol.bit true, HeadMove.right)
      else (symbols j, HeadMove.stay)) T, ?_⟩
  rw [Function.iterate_one]
  funext j
  by_cases hj : j = i
  · rw [hj]
    have hcell : Tape.move (Tape.write (T i) (TapeSymbol.bit true))
        HeadMove.right = cellsTape (TapeSymbol.bit true :: L) R.tail := by
      rw [hT, write_cellsTape]
      exact cellsTape_moveRight L (TapeSymbol.bit true) R.tail
    simp [writeMark, TypedMachine.step, TypedMachine.act,
      TypedMachine.startCfg, hcell]
  · simp [writeMark, TypedMachine.step, TypedMachine.act,
      TypedMachine.startCfg, hj, Tape.write_head_self, Tape.move]

/-- Tally one input onto a target, rewinding only the input. -/
def tallyOnto (s w : Fin tapes) :=
  (guidedWalk s w HeadMove.right (some (TapeSymbol.bit true))).andThen fun _ =>
    rewindRun s

set_option maxHeartbeats 4000000 in
/-- **One tally.**  The target gains one mark per cell of the input and its head
sits past them; the input is restored. -/
theorem tallyOnto_spec (s w : Fin tapes) (hsw : s ≠ w)
    (x Ls Rs Lw Rw : List TapeSymbol) (T : Fin tapes → Tape)
    (hnb : ∀ c ∈ x, c ≠ TapeSymbol.blank)
    (hs : T s = cellsTape (TapeSymbol.blank :: Ls)
      (x ++ TapeSymbol.blank :: Rs))
    (hw : T w = cellsTape Lw Rw) :
    ∃ cost : Nat,
      HaltsExactly (tallyOnto s w) ((tallyOnto s w).startCfg T) cost true ∧
      (((tallyOnto s w).step^[cost]) ((tallyOnto s w).startCfg T)).tape =
        Function.update T w
          (cellsTape (List.replicate x.length (TapeSymbol.bit true) ++ Lw)
            (Rw.drop x.length)) := by
  classical
  obtain ⟨hia, hib⟩ := guidedStep_write_iterate s w hsw x T
    (TapeSymbol.blank :: Ls) (TapeSymbol.blank :: Rs) Lw Rw (by rw [hs]) hw
  obtain ⟨hW, hWt⟩ := guidedWalk_spec s w hsw HeadMove.right
    (some (TapeSymbol.bit true)) x.length T
    (guidedStep_write_marks s w hsw x T (TapeSymbol.blank :: Ls)
      (TapeSymbol.blank :: Rs) Lw Rw hnb (by rw [hs]) hw)
    (by rw [hia]; rfl)
  set T1 := ((guidedStep s w HeadMove.right
    (some (TapeSymbol.bit true)))^[x.length]) T with hT1
  have hT1s : T1 s = cellsTape (x.reverse ++ TapeSymbol.blank :: Ls)
      (TapeSymbol.blank :: Rs) := hia
  obtain ⟨hR, hRt⟩ := rewindRun_spec s x Ls Rs TapeSymbol.blank T1 hnb
    (by rw [hT1s])
  have hch := chainStepC hW hWt hR
  refine ⟨_, hch.1, ?_⟩
  have hfin : ((tallyOnto s w).step^[_])
      ((tallyOnto 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_of_ne hsw, hs]
  · rw [Function.update_of_ne hj]
    by_cases hj2 : j = w
    · subst hj2
      rw [Function.update_self]
      exact hib
    · rw [Function.update_of_ne hj2, hT1,
        guidedStep_other s w HeadMove.right (some (TapeSymbol.bit true))
          x.length T j hj hj2]

/-! ## The clock, assembled -/

/-- Two marks, then one tally per input. -/
def clockSetup (s0 s1 s2 clk : Fin tapes) :=
  (writeMark clk).andThen fun _ =>
    (writeMark clk).andThen fun _ =>
      (tallyOnto s0 clk).andThen fun _ =>
        (tallyOnto s1 clk).andThen fun _ =>
          tallyOnto s2 clk

set_option maxHeartbeats 4000000 in
/-- **The clock, long enough.**  From a virgin clock tape the machine leaves
`|x0| + |x1| + |x2| + 2` marks with the head past all of them, every input
restored. -/
theorem clockSetup_spec (s0 s1 s2 clk : Fin tapes)
    (h0 : s0 ≠ clk) (h1 : s1 ≠ clk) (h2 : s2 ≠ clk)
    (x0 x1 x2 L0 L1 L2 R0 R1 R2 : List TapeSymbol) (T : Fin tapes → Tape)
    (hn0 : ∀ c ∈ x0, c ≠ TapeSymbol.blank)
    (hn1 : ∀ c ∈ x1, c ≠ TapeSymbol.blank)
    (hn2 : ∀ c ∈ x2, c ≠ TapeSymbol.blank)
    (hs0 : T s0 = cellsTape (TapeSymbol.blank :: L0)
      (x0 ++ TapeSymbol.blank :: R0))
    (hs1 : T s1 = cellsTape (TapeSymbol.blank :: L1)
      (x1 ++ TapeSymbol.blank :: R1))
    (hs2 : T s2 = cellsTape (TapeSymbol.blank :: L2)
      (x2 ++ TapeSymbol.blank :: R2))
    (hclk : T clk = cellsTape [TapeSymbol.blank] []) :
    ∃ cost : Nat,
      HaltsExactly (clockSetup s0 s1 s2 clk)
        ((clockSetup s0 s1 s2 clk).startCfg T) cost true ∧
      (((clockSetup s0 s1 s2 clk).step^[cost])
        ((clockSetup s0 s1 s2 clk).startCfg T)).tape =
        Function.update T clk
          (cellsTape (List.replicate
            (x2.length + (x1.length + (x0.length + 2))) (TapeSymbol.bit true)
            ++ [TapeSymbol.blank]) []) := by
  classical
  obtain ⟨gA, sA⟩ := writeMark_spec clk [TapeSymbol.blank] [] T hclk
  set TA := Function.update T clk
    (cellsTape (TapeSymbol.bit true :: [TapeSymbol.blank])
      ([] : List TapeSymbol).tail) with hTA
  have hTAclk : TA clk = cellsTape
      (List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] := by
    rw [hTA, Function.update_self]
    simp
  obtain ⟨gB, sB⟩ := writeMark_spec clk
    (List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] TA hTAclk
  set TB := Function.update TA clk
    (cellsTape (TapeSymbol.bit true ::
      (List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]))
      ([] : List TapeSymbol).tail) with hTB
  have hTBclk : TB clk = cellsTape
      (List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] := by
    rw [hTB, Function.update_self]
    simp [List.replicate_succ]
  have hTBs : ∀ (s : Fin tapes), s ≠ clk → TB s = T s := by
    intro s hs
    rw [hTB, Function.update_of_ne hs, hTA, Function.update_of_ne hs]
  obtain ⟨c1, g1, t1⟩ := tallyOnto_spec s0 clk h0 x0 L0 R0
    (List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] TB hn0
    (by rw [hTBs s0 h0]; exact hs0) hTBclk
  set T1 := Function.update TB clk
    (cellsTape (List.replicate x0.length (TapeSymbol.bit true) ++
      (List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]))
      (([] : List TapeSymbol).drop x0.length)) with hT1
  have hT1clk : T1 clk = cellsTape
      (List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
        [TapeSymbol.blank]) [] := by
    rw [hT1, Function.update_self, ← List.append_assoc, ← List.replicate_add]
    simp
  have hT1s : ∀ (s : Fin tapes), s ≠ clk → T1 s = T s := by
    intro s hs
    rw [hT1, Function.update_of_ne hs]
    exact hTBs s hs
  obtain ⟨c2, g2, t2⟩ := tallyOnto_spec s1 clk h1 x1 L1 R1
    (List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
      [TapeSymbol.blank]) [] T1 hn1
    (by rw [hT1s s1 h1]; exact hs1) hT1clk
  set T2 := Function.update T1 clk
    (cellsTape (List.replicate x1.length (TapeSymbol.bit true) ++
      (List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
        [TapeSymbol.blank]))
      (([] : List TapeSymbol).drop x1.length)) with hT2
  have hT2clk : T2 clk = cellsTape
      (List.replicate (x1.length + (x0.length + 2)) (TapeSymbol.bit true) ++
        [TapeSymbol.blank]) [] := by
    rw [hT2, Function.update_self, ← List.append_assoc, ← List.replicate_add]
    simp
  have hT2s : ∀ (s : Fin tapes), s ≠ clk → T2 s = T s := by
    intro s hs
    rw [hT2, Function.update_of_ne hs]
    exact hT1s s hs
  obtain ⟨c3, g3, t3⟩ := tallyOnto_spec s2 clk h2 x2 L2 R2
    (List.replicate (x1.length + (x0.length + 2)) (TapeSymbol.bit true) ++
      [TapeSymbol.blank]) [] T2 hn2
    (by rw [hT2s s2 h2]; exact hs2) hT2clk
  have k3 := chainStepC g2 t2 g3
  have k2 := chainStepC g1 t1 k3.1
  have k1 := chainStepC gB sB k2.1
  have k0 := chainStepC gA sA k1.1
  refine ⟨_, k0.1, ?_⟩
  have hfin := k0.2
  rw [k1.2, k2.2, k3.2] at hfin
  have hfin' : ((clockSetup s0 s1 s2 clk).step^[_])
      ((clockSetup s0 s1 s2 clk).startCfg T) = _ := hfin
  rw [hfin']
  show (((tallyOnto s2 clk).step^[c3])
    ((tallyOnto s2 clk).startCfg T2)).tape = _
  rw [t3]
  funext j
  by_cases hj : j = clk
  · subst hj
    rw [Function.update_self, Function.update_self, ← List.append_assoc,
      ← List.replicate_add]
    simp
  · rw [Function.update_of_ne hj, Function.update_of_ne hj]
    exact hT2s j hj

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