Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The track update, ghost-uniform, with region bound

Definition
sgl_update_uniform

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The track update with cost, output region, and region length fixed before the ghost.

Successor to sgl_step_uniform. That module fixed the cost and output region ahead of the ghost — necessary because a read phase hands its continuation an arbitrary one — but did not bound the output region's length. Without that bound the second of two chained updates has a cost expressed in terms of a region of unknown size, and the composed step is not visibly polynomial. Each of the five variants either preserves the region's length or extends it by the single materialised block, so ∣blocks′∣≤∣blocks∣+1|{\rm blocks}'| \le |{\rm blocks}| + 1∣blocks′∣≤∣blocks∣+1; it simply has to be stated.

IdentPart separates the non-host component of the invariant so it can be carried across an update without mentioning the host tape at all. The result is one fact — cost bounded by 100∣blocks∣+300100|{\rm blocks}| + 300100∣blocks∣+300, region growth by at most one, and MergeInv re-established with the updated track's virtual tape written and moved — valid at any ghost.

Definition code
import Definitions.Def_sgl_step_pieces

/-!
# The track update, ghost-uniform (with region bound)

Module E3b, second part.  Successor to `sgl_step_uniform`, which lacked the
output-region length bound; that bound is needed to keep the *second* update's
cost expressible in terms of the *first* update's input, hence to keep the
composed step polynomial.  Platform definitions being immutable, this is a new
module rather than an edit.

`updateTrack_step` takes the invariant — hence a *fixed* physical tape — and
produces its cost existentially.  The per-step composition needs the opposite
order: the read phases hand their continuation an arbitrary ghost, so the cost
and the resulting region must be fixed **before** the ghost is chosen.

The bounded specifications already have that shape, so the hoist is direct:
this module redoes `updateTrack_step`'s case analysis with the ghost
introduced inside, yielding one cost and one output region valid for every
ghost.
-/

namespace SipserGacsLautemann

variable {states : Nat}

/-- The non-host component of the invariant, separated so it can be carried
across an update without mentioning the host tape. -/
def IdentPart (tapes' : Nat) (virt : Configuration (tapes' + 2) states)
    (base : Fin (tapes' + 1) → Tape) : Prop :=
  ∀ j : Fin (tapes' + 1), j.val < tapes' → base j = virt.tape ⟨j.val, by omega⟩

theorem identPart_update {tapes' : Nat} {virt : Configuration (tapes' + 2) states}
    {base : Fin (tapes' + 1) → Tape} (h : IdentPart tapes' virt base)
    (side : TrackSide) (X : Tape) (Y : Tape) :
    IdentPart tapes'
      { state := virt.state
        tape := Function.update virt.tape (hostIdx tapes' side) X }
      (Function.update base (Fin.last tapes') Y) := by
  intro j hj
  have hne : j ≠ Fin.last tapes' := by
    intro hcon; rw [hcon] at hj; simp at hj
  have hne2 : (⟨j.val, by omega⟩ : Fin (tapes' + 2)) ≠ hostIdx tapes' side := by
    intro hcon
    have := congrArg Fin.val hcon
    cases side <;> simp [hostIdx] at this <;> omega
  rw [Function.update_of_ne hne]
  show base j = Function.update virt.tape (hostIdx tapes' side) X _
  rw [Function.update_of_ne hne2]
  exact h j hj

/-- **The update, with cost and output region fixed before the ghost.** -/
theorem updateTrack_step_u {tapes' : Nat}
    (virt : Configuration (tapes' + 2) states)
    (base : Fin (tapes' + 1) → Tape) (blocks : List Block)
    (side : TrackSide) (s : TapeSymbol) (mv : HeadMove)
    (hident : IdentPart tapes' virt base)
    (hosts : HostsPair blocks (fun sd => virt.tape (hostIdx tapes' sd))) :
    ∃ (cost : Nat) (blocks' : List Block),
      cost ≤ 100 * blocks.length + 300 ∧
      blocks'.length ≤ blocks.length + 1 ∧
      ∀ (G : List TapeSymbol), AllBlank G →
        HaltsExactly (updateTrack side (Fin.last tapes') s mv)
          ((updateTrack side (Fin.last tapes') s mv).startCfg
            (Function.update base (Fin.last tapes')
              (ParkedTape blocks G))) cost false ∧
        ∃ G', AllBlank G' ∧
          (((updateTrack side (Fin.last tapes') s mv).step^[cost])
            ((updateTrack side (Fin.last tapes') s mv).startCfg
              (Function.update base (Fin.last tapes')
                (ParkedTape blocks G)))).tape =
            Function.update base (Fin.last tapes')
              (ParkedTape blocks' G') ∧
          MergeInv tapes'
            { state := virt.state
              tape := Function.update virt.tape (hostIdx tapes' side)
                (Tape.move
                  (Tape.write (virt.tape (hostIdx tapes' side)) s) mv) }
            (Function.update base (Fin.last tapes')
              (ParkedTape blocks' G')) blocks' G' := by
  classical
  obtain ⟨pre, cur, post, hsplit, -⟩ := hosts side
  have hblocks := hsplit.eq
  subst hblocks
  have hpk : ∀ (bl : List Block) (Gx : List TapeSymbol),
      (Function.update base (Fin.last tapes') (ParkedTape bl Gx))
        (Fin.last tapes') = ParkedTape bl Gx := by
    intro bl Gx; simp
  have hstart : ∀ (Gx : List TapeSymbol),
      (Function.update base (Fin.last tapes') (ParkedTape (pre ++ cur :: post) Gx))
        (Fin.last tapes') = ParkedTape (pre ++ cur :: post) Gx := fun Gx => hpk _ _
  cases mv with
  | stay =>
      obtain ⟨cost, hbound, hrun⟩ := updateTrack_stay_bounded side
        (Fin.last tapes') s pre cur post hsplit.preClear hsplit.curSet
      refine ⟨cost, pre ++ setSymFlag side s true cur :: post, hbound,
        by simp, ?_⟩
      intro G hG
      obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG (hstart G)
      rw [Function.update_idem] at htape
      refine ⟨hhalt, G', hG', htape, identPart_update hident side _ _,
        hpk _ _, hG', ?_⟩
      have hp := hosts.update_stay side hsplit s
      simp only [virtTape_update_apply]
      exact hp
  | right =>
      cases post with
      | cons nxt post' =>
          obtain ⟨cost, hbound, hrun⟩ := updateTrack_right_cons_bounded side
            (Fin.last tapes') s pre cur nxt post' hsplit.preClear hsplit.curSet
          refine ⟨cost, pre ++ setSymFlag side s false cur ::
            setFlag side true nxt :: post', hbound, by simp, ?_⟩
          intro G hG
          obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG (hstart G)
          rw [Function.update_idem] at htape
          refine ⟨hhalt, G', hG', htape, identPart_update hident side _ _,
            hpk _ _, hG', ?_⟩
          have hp := hosts.update_right_mid side hsplit s
          simp only [virtTape_update_apply]
          exact hp
      | nil =>
          obtain ⟨cost, hbound, hrun⟩ := updateTrack_right_nil_bounded side
            (Fin.last tapes') s pre cur hsplit.preClear hsplit.curSet
          refine ⟨cost, pre ++ [setSymFlag side s false cur,
            freshFlagged side], hbound, by simp, ?_⟩
          intro G hG
          obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG (hstart G)
          rw [Function.update_idem] at htape
          refine ⟨hhalt, G', hG', htape, identPart_update hident side _ _,
            hpk _ _, hG', ?_⟩
          have hp := hosts.update_right_edge side hsplit s
          simp only [virtTape_update_apply]
          exact hp
  | left =>
      rcases List.eq_nil_or_concat pre with rfl | ⟨pre', prv, rfl⟩
      · obtain ⟨cost, hbound, hrun⟩ := updateTrack_left_nil_bounded side
          (Fin.last tapes') s cur post hsplit.curSet
        refine ⟨cost, freshFlagged side ::
          setSymFlag side s false cur :: post, hbound, by simp, ?_⟩
        intro G hG
        obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG
          (by have h := hstart G; simp only [List.nil_append] at h; exact h)
        rw [Function.update_idem] at htape
        refine ⟨by simpa using hhalt, G', hG', by simpa using htape,
          identPart_update hident side _ _, hpk _ _, hG', ?_⟩
        have hp := hosts.update_left_edge side (by simpa using hsplit) s
        simp only [virtTape_update_apply]
        exact hp
      · simp only [List.concat_eq_append] at *
        obtain ⟨cost, hbound, hrun⟩ := updateTrack_left_concat_bounded side
          (Fin.last tapes') s pre' prv cur post hsplit.preClear hsplit.curSet
        refine ⟨cost, pre' ++ setFlag side true prv ::
          setSymFlag side s false cur :: post, hbound, by simp, ?_⟩
        intro G hG
        obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG (hstart G)
        rw [Function.update_idem] at htape
        refine ⟨hhalt, G', hG', htape, identPart_update hident side _ _,
          hpk _ _, hG', ?_⟩
        have hp := hosts.update_left_mid side hsplit s
        simp only [virtTape_update_apply]
        exact hp

end SipserGacsLautemann
Source
Ghost-uniform track update with output-region bound; successor to Def_sgl_step_uniform.

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