Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_finite_override

Definition

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

complexity-theoryfinite-languageturing-machine

An explicit finite-state scan machine for the short-input branch of a polynomial-time decider. It records at most a fixed threshold of input bits and proves exact acceptance and rejection behavior for the resulting finite language override.

Definition code
import Definitions.Def_sgl_machine_infrastructure
import Mathlib.Data.Fintype.Basic
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.Fintype.Sum
import Mathlib.Data.List.GetD

namespace SipserGacsLautemann

open scoped Classical

structure ShortScanData (threshold : Nat) where
  length : Fin (threshold + 1)
  bits : BitString threshold

def ShortScanData.equivProd (threshold : Nat) :
    ShortScanData threshold ≃
      Fin (threshold + 1) × BitString threshold where
  toFun data := (data.length, data.bits)
  invFun data := ⟨data.1, data.2⟩
  left_inv data := by cases data; rfl
  right_inv data := by cases data; rfl

noncomputable instance (threshold : Nat) :
    Fintype (ShortScanData threshold) :=
  Fintype.ofEquiv
    (Fin (threshold + 1) × BitString threshold)
    (ShortScanData.equivProd threshold).symm

inductive ShortMachineState (threshold : Nat) where
  | scan : ShortScanData threshold → ShortMachineState threshold
  | accept : ShortMachineState threshold
  | reject : ShortMachineState threshold

def ShortMachineState.equivSum (threshold : Nat) :
    ShortMachineState threshold ≃ ShortScanData threshold ⊕ Bool where
  toFun
    | .scan data => Sum.inl data
    | .accept => Sum.inr true
    | .reject => Sum.inr false
  invFun
    | Sum.inl data => .scan data
    | Sum.inr true => .accept
    | Sum.inr false => .reject
  left_inv state := by cases state <;> rfl
  right_inv state := by
    cases state with
    | inl data => rfl
    | inr result => cases result <;> rfl

noncomputable instance (threshold : Nat) :
    Fintype (ShortMachineState threshold) :=
  Fintype.ofEquiv
    (ShortScanData threshold ⊕ Bool)
    (ShortMachineState.equivSum threshold).symm

def ShortScanData.toList {threshold : Nat}
    (data : ShortScanData threshold) : List Bool :=
  List.ofFn fun i : Fin data.length.val =>
    data.bits
      ⟨i.val,
        i.isLt.trans_le (Nat.lt_succ_iff.mp data.length.isLt)⟩

def shortMachineStartData (threshold : Nat) :
    ShortScanData threshold :=
  ⟨⟨0, Nat.zero_lt_succ threshold⟩, fun _ => false⟩

def ShortScanData.push {threshold : Nat}
    (data : ShortScanData threshold) (bit : Bool)
    (h : data.length.val < threshold) :
    ShortScanData threshold :=
  { length :=
      ⟨data.length.val + 1, Nat.succ_lt_succ h⟩
    bits :=
      Function.update data.bits
        ⟨data.length.val, h⟩ bit }

def preserveAll {tapes : Nat}
    (symbols : Fin tapes → TapeSymbol) :
    Fin tapes → TapeSymbol × HeadMove :=
  fun i => (symbols i, .stay)

def moveFirstRight {tapes : Nat}
    (symbols : Fin (tapes + 1) → TapeSymbol) :
    Fin (tapes + 1) → TapeSymbol × HeadMove :=
  fun i =>
    if h : i.val = 0 then (symbols i, .right)
    else (symbols i, .stay)

def firstTapeIndex (tapes : Nat) : Fin (tapes + 1) :=
  ⟨0, Nat.zero_lt_succ tapes⟩

noncomputable def shortLanguageTypedMachine
    (language : Language) (threshold tapes : Nat) :
    TypedMachine (tapes + 1) (ShortMachineState threshold) := by
  classical
  exact
    { start := .scan (shortMachineStartData threshold)
      transition := fun state symbols =>
        match state with
        | .accept => (.accept, preserveAll symbols)
        | .reject => (.reject, preserveAll symbols)
        | .scan data =>
            match symbols (firstTapeIndex tapes) with
            | .blank =>
                if data.length.val < threshold ∧
                    data.toList ∈ language then
                  (.accept, preserveAll symbols)
                else
                  (.reject, preserveAll symbols)
            | .bit bit =>
                if h : data.length.val < threshold then
                  (.scan (data.push bit h), moveFirstRight symbols)
                else
                  (.reject, preserveAll symbols)
      result := fun state =>
        match state with
        | .accept => some true
        | .reject => some false
        | .scan _ => none }

def ShortScanData.ofList {threshold : Nat} (bits : List Bool)
    (hbits : bits.length ≤ threshold) : ShortScanData threshold :=
  { length := ⟨bits.length, Nat.lt_succ_of_le hbits⟩
    bits := fun i => bits.getD i.val false }

theorem ShortScanData.toList_ofList {threshold : Nat}
    (bits : List Bool) (hbits : bits.length ≤ threshold) :
    (ShortScanData.ofList bits hbits).toList = bits := by
  apply List.ext_get
  · simp [ShortScanData.toList, ShortScanData.ofList]
  · intro n h₁ h₂
    simp only [ShortScanData.toList, ShortScanData.ofList,
      List.get_eq_getElem, List.getElem_ofFn]
    rw [List.getD_eq_getElem _ _ h₂]

theorem ShortScanData.push_ofList {threshold : Nat}
    (bits : List Bool) (hbits : bits.length < threshold)
    (bit : Bool) :
    (ShortScanData.ofList bits (Nat.le_of_lt hbits)).push bit hbits =
      ShortScanData.ofList (bits ++ [bit])
        (by simpa using Nat.succ_le_of_lt hbits) := by
  apply (ShortScanData.equivProd threshold).injective
  change
    (((ShortScanData.ofList bits (Nat.le_of_lt hbits)).push bit hbits).length,
      ((ShortScanData.ofList bits (Nat.le_of_lt hbits)).push bit hbits).bits) =
    ((ShortScanData.ofList (bits ++ [bit])
      (by simpa using Nat.succ_le_of_lt hbits)).length,
      (ShortScanData.ofList (bits ++ [bit])
        (by simpa using Nat.succ_le_of_lt hbits)).bits)
  apply Prod.ext
  · apply Fin.ext
    simp [ShortScanData.push, ShortScanData.ofList]
  · funext i
    simp only [ShortScanData.push, ShortScanData.ofList]
    by_cases hi : i.val = bits.length
    · have hiFin : i = ⟨bits.length, hbits⟩ :=
        Fin.ext hi
      subst i
      simp
    · have hi' : i.val < bits.length ∨ bits.length < i.val :=
        lt_or_gt_of_ne hi
      rcases hi' with hi' | hi'
      · rw [Function.update_of_ne]
        · exact List.getD_append bits [bit] false i.val hi' |>.symm
        · intro heq
          exact hi (Fin.ext_iff.mp heq)
      · have hout : bits.length + 1 ≤ i.val := Nat.succ_le_iff.mpr hi'
        rw [Function.update_of_ne]
        · rw [List.getD_eq_default _ _]
          · rw [List.getD_eq_default _ _]
            simpa using hout
          · exact hi'.le
        · intro heq
          exact hi (Fin.ext_iff.mp heq)

theorem Tape.write_head_eq (tape : Tape) :
    Tape.write tape tape.head = tape := by
  cases tape
  rfl

theorem Tape.iterate_move_right_head (tape : Tape) (steps : Nat) :
    (((Tape.move · .right)^[steps]) tape).head =
      (tape.head :: tape.right).getD steps .blank := by
  induction steps generalizing tape with
  | zero => rfl
  | succ steps ih =>
      rw [Function.iterate_succ_apply]
      rw [ih]
      cases tape with
      | mk left head right =>
          cases right with
          | nil =>
              simp [Tape.move, List.getD_eq_default]
          | cons next rest =>
              simp [Tape.move, List.getD]

theorem Tape.iterate_move_right_ofBits_head_of_lt
    (bits : List Bool) {steps : Nat} (hsteps : steps < bits.length) :
    (((Tape.move · .right)^[steps]) (Tape.ofBits bits)).head =
      .bit bits[steps] := by
  rw [Tape.iterate_move_right_head]
  cases bits with
  | nil => simp at hsteps
  | cons first rest =>
      simp only [Tape.ofBits]
      rw [show
        (TapeSymbol.bit first :: List.map TapeSymbol.bit rest) =
          List.map TapeSymbol.bit (first :: rest) by rfl]
      rw [List.getD_eq_getElem _ _
        (by simpa using hsteps)]
      cases steps <;> simp

theorem Tape.iterate_move_right_ofBits_head_length
    (bits : List Bool) :
    (((Tape.move · .right)^[bits.length]) (Tape.ofBits bits)).head =
      .blank := by
  rw [Tape.iterate_move_right_head]
  cases bits with
  | nil => rfl
  | cons first rest =>
      simp only [Tape.ofBits]
      rw [show
        (TapeSymbol.bit first :: List.map TapeSymbol.bit rest) =
          List.map TapeSymbol.bit (first :: rest) by rfl]
      rw [List.getD_eq_default]
      simp

theorem shortLanguageTypedMachine_step_scan_bit
    (language : Language) (threshold tapes : Nat)
    (configuration :
      TypedConfiguration (tapes + 1) (ShortMachineState threshold))
    (data : ShortScanData threshold) (bit : Bool)
    (hstate : configuration.state = .scan data)
    (hhead :
      (configuration.tape (firstTapeIndex tapes)).head = .bit bit)
    (hlength : data.length.val < threshold) :
    ((shortLanguageTypedMachine language threshold tapes).step
        configuration).state =
        .scan (data.push bit hlength) ∧
      ((shortLanguageTypedMachine language threshold tapes).step
        configuration).tape (firstTapeIndex tapes) =
        Tape.move
          (configuration.tape (firstTapeIndex tapes)) .right := by
  unfold TypedMachine.step
  rw [hstate]
  simp only [shortLanguageTypedMachine]
  rw [hhead]
  simp only
  rw [dif_pos hlength]
  constructor
  · rfl
  · simp [moveFirstRight, firstTapeIndex, Tape.write_head_eq]

theorem shortLanguageTypedMachine_run_scan
    (language : Language) (threshold tapes : Nat)
    (input : Fin (tapes + 1) → List Bool)
    (steps : Nat)
    (hthreshold : steps ≤ threshold)
    (hinput : steps ≤ (input (firstTapeIndex tapes)).length) :
    ((shortLanguageTypedMachine language threshold tapes).run
          input steps).state =
        .scan
          (ShortScanData.ofList
            ((input (firstTapeIndex tapes)).take steps)
            ((List.length_take_le _ _).trans hthreshold)) ∧
      ((shortLanguageTypedMachine language threshold tapes).run
          input steps).tape (firstTapeIndex tapes) =
        (((Tape.move · .right)^[steps])
          (Tape.ofBits (input (firstTapeIndex tapes)))) := by
  induction steps with
  | zero =>
      dsimp [TypedMachine.run, TypedMachine.initialConfiguration,
        shortLanguageTypedMachine, firstTapeIndex]
      constructor
      · congr 2
      · rfl
  | succ steps ih =>
      have hstepsThreshold : steps < threshold :=
        Nat.lt_of_succ_le hthreshold
      have hstepsInput :
          steps < (input (firstTapeIndex tapes)).length :=
        Nat.lt_of_succ_le hinput
      have ih' :=
        ih (Nat.le_of_lt hstepsThreshold) (Nat.le_of_lt hstepsInput)
      let scanned :=
        (input (firstTapeIndex tapes)).take steps
      have hprefixLength :
          scanned.length = steps := by
        exact List.length_take_of_le (Nat.le_of_lt hstepsInput)
      have hprefixThreshold : scanned.length < threshold := by
        rw [hprefixLength]
        exact hstepsThreshold
      have hhead :
          ((((shortLanguageTypedMachine language threshold tapes).run
              input steps).tape (firstTapeIndex tapes)).head) =
            .bit (input (firstTapeIndex tapes))[steps] := by
        rw [ih'.2]
        exact
          Tape.iterate_move_right_ofBits_head_of_lt
            (input (firstTapeIndex tapes)) hstepsInput
      have hstep :=
        shortLanguageTypedMachine_step_scan_bit
          language threshold tapes
          ((shortLanguageTypedMachine language threshold tapes).run
            input steps)
          (ShortScanData.ofList
            ((input (firstTapeIndex tapes)).take steps)
            ((List.length_take_le _ _).trans
              (Nat.le_of_lt hstepsThreshold)))
          (input (firstTapeIndex tapes))[steps]
          ih'.1 hhead
          (by
            change
              ((input (firstTapeIndex tapes)).take steps).length <
                threshold
            simpa only [scanned] using hprefixThreshold)
      rw [TypedMachine.run]
      constructor
      · have htakeSucc :
            (input (firstTapeIndex tapes)).take (steps + 1) =
              scanned ++
                [(input (firstTapeIndex tapes))[steps]] := by
          simpa [scanned] using
            (List.take_succ_eq_append_getElem hstepsInput)
        have hpush :=
          ShortScanData.push_ofList scanned hprefixThreshold
            (input (firstTapeIndex tapes))[steps]
        have hdata :
            (ShortScanData.ofList
                ((input (firstTapeIndex tapes)).take steps)
                ((List.length_take_le _ _).trans
                  (Nat.le_of_lt hstepsThreshold))).push
                (input (firstTapeIndex tapes))[steps]
                (by
                  change
                    ((input (firstTapeIndex tapes)).take steps).length <
                      threshold
                  simpa only [scanned] using hprefixThreshold) =
              ShortScanData.ofList
                ((input (firstTapeIndex tapes)).take (steps + 1))
                ((List.length_take_le _ _).trans hthreshold) := by
          simpa only [scanned, htakeSucc] using hpush
        exact hstep.1.trans (congrArg ShortMachineState.scan hdata)
      · rw [hstep.2, ih'.2]
        rw [Function.iterate_succ_apply']

theorem shortLanguageTypedMachine_step_scan_blank
    (language : Language) (threshold tapes : Nat)
    (configuration :
      TypedConfiguration (tapes + 1) (ShortMachineState threshold))
    (data : ShortScanData threshold)
    (hstate : configuration.state = .scan data)
    (hhead :
      (configuration.tape (firstTapeIndex tapes)).head = .blank) :
    ((shortLanguageTypedMachine language threshold tapes).step
        configuration).state =
      if data.length.val < threshold ∧ data.toList ∈ language then
        ShortMachineState.accept
      else
        ShortMachineState.reject := by
  unfold TypedMachine.step
  rw [hstate]
  simp only [shortLanguageTypedMachine]
  rw [hhead]
  by_cases hcondition :
      data.length.val < threshold ∧ data.toList ∈ language
  · simp [hcondition]
  · simp [hcondition]

theorem shortLanguageTypedMachine_step_scan_of_not_lt
    (language : Language) (threshold tapes : Nat)
    (configuration :
      TypedConfiguration (tapes + 1) (ShortMachineState threshold))
    (data : ShortScanData threshold)
    (hstate : configuration.state = .scan data)
    (hlength : ¬data.length.val < threshold) :
    ((shortLanguageTypedMachine language threshold tapes).step
        configuration).state = .reject := by
  unfold TypedMachine.step
  rw [hstate]
  simp only [shortLanguageTypedMachine]
  cases hsymbol :
      (configuration.tape (firstTapeIndex tapes)).head with
  | blank =>
      simp [hlength]
  | bit bit =>
      simp [hlength]

theorem shortLanguageTypedMachine_result_at_bound
    (language : Language) (threshold tapes : Nat)
    (input : Fin (tapes + 1) → List Bool) :
    (shortLanguageTypedMachine language threshold tapes).result
        ((shortLanguageTypedMachine language threshold tapes).run
          input (threshold + 1)).state =
      some
        (decide
          ((input (firstTapeIndex tapes)).length < threshold ∧
            input (firstTapeIndex tapes) ∈ language)) := by
  classical
  let machine := shortLanguageTypedMachine language threshold tapes
  let bits := input (firstTapeIndex tapes)
  change
    machine.result (machine.run input (threshold + 1)).state =
      some (decide (bits.length < threshold ∧ bits ∈ language))
  by_cases hshort : bits.length < threshold
  · have hscan :=
      shortLanguageTypedMachine_run_scan
        language threshold tapes input bits.length
        (Nat.le_of_lt hshort) le_rfl
    have hhead :
        ((machine.run input bits.length).tape
          (firstTapeIndex tapes)).head = .blank := by
      rw [hscan.2]
      exact Tape.iterate_move_right_ofBits_head_length bits
    have hstep :=
      shortLanguageTypedMachine_step_scan_blank
        language threshold tapes (machine.run input bits.length)
        (ShortScanData.ofList bits (Nat.le_of_lt hshort))
        (by
          simpa [machine, bits, List.take_length] using hscan.1)
        hhead
    rw [ShortScanData.toList_ofList] at hstep
    simp only [ShortScanData.ofList] at hstep
    simp only [hshort, true_and] at hstep
    have hresultEarly :
        machine.result
            (machine.run input (bits.length + 1)).state =
          some (decide (bits ∈ language)) := by
      rw [TypedMachine.run]
      rw [hstep]
      by_cases hmember : bits ∈ language
      · simp [machine, shortLanguageTypedMachine,
          ShortScanData.ofList, hshort, hmember]
      · simp [machine, shortLanguageTypedMachine,
          ShortScanData.ofList, hshort, hmember]
    obtain ⟨extra, hextra⟩ :=
      Nat.exists_eq_add_of_le (Nat.succ_le_succ (Nat.le_of_lt hshort))
    have hextra' :
        threshold + 1 = (bits.length + 1) + extra := by
      omega
    rw [hextra']
    rw [machine.run_add_eq_of_result_run_eq_some
      input (bits.length + 1) extra hresultEarly]
    simpa [hshort] using hresultEarly
  · have hscan :=
      shortLanguageTypedMachine_run_scan
        language threshold tapes input threshold le_rfl
        (Nat.le_of_not_gt hshort)
    have hstep :=
      shortLanguageTypedMachine_step_scan_of_not_lt
        language threshold tapes (machine.run input threshold)
        (ShortScanData.ofList (bits.take threshold)
          (List.length_take_le _ _))
        (by simpa [machine, bits] using hscan.1)
        (by
          simp [ShortScanData.ofList,
            List.length_take_of_le (Nat.le_of_not_gt hshort)])
    rw [TypedMachine.run, hstep]
    simp [machine, shortLanguageTypedMachine, hshort]

theorem decidesInPolynomialTime_shortLanguage
    (language : Language) (threshold tapes : Nat) :
    DecidesInPolynomialTime
      (fun input : Fin (tapes + 1) → List Bool =>
        (input (firstTapeIndex tapes)).length < threshold ∧
          input (firstTapeIndex tapes) ∈ language) := by
  classical
  let typedMachine :=
    shortLanguageTypedMachine language threshold tapes
  let machine := typedMachine.toMachine
  let time : Nat → Nat := fun _ => threshold + 1
  refine
    ⟨Fintype.card (ShortMachineState threshold), machine, time,
      ⟨threshold + 1, 0, by
        intro n
        simp [time]⟩, ?_⟩
  intro input
  have hresult :=
    shortLanguageTypedMachine_result_at_bound
      language threshold tapes input
  constructor
  · rw [typedMachine.toMachine_acceptsWithin_iff]
    constructor
    · intro haccept
      simpa [typedMachine, time] using
        show
          decide
              ((input (firstTapeIndex tapes)).length < threshold ∧
                input (firstTapeIndex tapes) ∈ language) =
            true by
          rw [← Option.some_inj]
          exact hresult.symm.trans haccept
    · intro hpredicate
      have hdecide :
          decide
              ((input (firstTapeIndex tapes)).length < threshold ∧
                input (firstTapeIndex tapes) ∈ language) = true :=
        by simpa using hpredicate
      simpa [typedMachine, time] using hresult.trans (congrArg some hdecide)
  · rw [typedMachine.toMachine_rejectsWithin_iff]
    constructor
    · intro hreject hpredicate
      have hdecide :
          decide
              ((input (firstTapeIndex tapes)).length < threshold ∧
                input (firstTapeIndex tapes) ∈ language) = true :=
        by simpa using hpredicate
      have : some true = some false :=
        (hresult.trans (congrArg some hdecide)).symm.trans hreject
      contradiction
    · intro hnotPredicate
      have hdecide :
          decide
              ((input (firstTapeIndex tapes)).length < threshold ∧
                input (firstTapeIndex tapes) ∈ language) = false := by
        simp [hnotPredicate]
      simpa [typedMachine, time] using hresult.trans (congrArg some hdecide)

end SipserGacsLautemann
Source
Reusable finite-exception construction for the custom Turing-machine model in the Sipser–Gács–Lautemann mission.

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