Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bounded unary-offset virtual input data

Definition
sgl_bounded_unary_offset_data

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

This module defines the virtual four-tape input used by the bounded-unary scheduler. Given a three-tape input (x,e,u)(x,e,u)(x,e,u) and a natural offset iii, it forms the four-tape input (x,e,u,1i)(x,e,u,1^i)(x,e,u,1i). It proves the exact total-length formula and the bound needed when i≤∣u∣i \le |u|i≤∣u∣: the virtual four-tape input has total length at most twice the original three-tape input length. It also defines a classical Boolean decision helper for whether the supplied base machine accepts at some bounded unary offset.

Definition code
import Definitions.Def_sipser_gacs_lautemann
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Tactic.FinCases

namespace SipserGacsLautemann

def boundedUnaryOffsetInput
    (input : Fin 3 → List Bool) (offset : Nat) :
    Fin 4 → List Bool :=
  fun j =>
    if j = 0 then input 0
    else if j = 1 then input 1
    else if j = 2 then input 2
    else List.replicate offset true

@[simp]
theorem boundedUnaryOffsetInput_zero
    (input : Fin 3 → List Bool) (offset : Nat) :
    boundedUnaryOffsetInput input offset 0 = input 0 := by
  simp [boundedUnaryOffsetInput]

@[simp]
theorem boundedUnaryOffsetInput_one
    (input : Fin 3 → List Bool) (offset : Nat) :
    boundedUnaryOffsetInput input offset 1 = input 1 := by
  simp [boundedUnaryOffsetInput]

@[simp]
theorem boundedUnaryOffsetInput_two
    (input : Fin 3 → List Bool) (offset : Nat) :
    boundedUnaryOffsetInput input offset 2 = input 2 := by
  simp [boundedUnaryOffsetInput]

@[simp]
theorem boundedUnaryOffsetInput_three
    (input : Fin 3 → List Bool) (offset : Nat) :
    boundedUnaryOffsetInput input offset 3 =
      List.replicate offset true := by
  simp [boundedUnaryOffsetInput]

theorem boundedUnaryOffsetInput_eq_original
    (input : Fin 3 → List Bool) (offset : Nat) :
    boundedUnaryOffsetInput input offset =
      fun j : Fin 4 =>
        if j = 0 then input 0
        else if j = 1 then input 1
        else if j = 2 then input 2
        else List.replicate offset true := by
  rfl

theorem totalInputLength_boundedUnaryOffsetInput
  (input : Fin 3 → List Bool) (offset : Nat) :
    totalInputLength (boundedUnaryOffsetInput input offset) =
      totalInputLength input + offset := by
  simp only [totalInputLength, List.sum_ofFn]
  rw [Fin.sum_univ_four, Fin.sum_univ_three]
  simp [boundedUnaryOffsetInput]

theorem totalInputLength_boundedUnaryOffsetInput_le
    (input : Fin 3 → List Bool)
    (offset : Fin ((input 2).length + 1)) :
    totalInputLength
        (boundedUnaryOffsetInput input offset.val) ≤
      2 * totalInputLength input := by
  rw [totalInputLength_boundedUnaryOffsetInput]
  have hoffset : offset.val ≤ (input 2).length :=
    Nat.lt_succ_iff.mp offset.isLt
  have hcomponent :
      (input 2).length ≤ totalInputLength input := by
    simp only [totalInputLength, List.sum_ofFn]
    rw [Fin.sum_univ_three]
    omega
  omega

def boundedUnaryOffsetBaseAccepts
    {states : Nat}
    (machine : Machine 4 states)
    (time : Nat → Nat)
    (input : Fin 3 → List Bool) : Prop :=
  ∃ offset : Fin ((input 2).length + 1),
    machine.acceptsWithin
      (boundedUnaryOffsetInput input offset.val)
      (time
        (totalInputLength
          (boundedUnaryOffsetInput input offset.val)))

noncomputable def boundedUnaryOffsetBaseAcceptDecision
    {states : Nat}
    (machine : Machine 4 states)
    (time : Nat → Nat)
    (input : Fin 3 → List Bool) : Bool :=
  @decide
    (boundedUnaryOffsetBaseAccepts machine time input)
    (Classical.propDecidable _)

end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission bounded-unary scheduler construction.

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