Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_finite_override_delegate

Definition

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

complexity-theorypolynomial-timeturing-machine

A sorry-free generic machine construction that decides a fixed finite language on inputs shorter than a threshold and otherwise restores the initial tapes exactly before delegating to an arbitrary polynomial-time base machine. It includes the exact run simulation and polynomial time bound.

Definition code
import Definitions.Def_sgl_finite_override
import Mathlib.Data.Fintype.Sum

namespace SipserGacsLautemann

inductive OverrideState (threshold baseStates : Nat) where
  | scan : ShortScanData threshold → OverrideState threshold baseStates
  | rewind : Fin (threshold + 1) → OverrideState threshold baseStates
  | base : Fin baseStates → OverrideState threshold baseStates
  | shortAccept : OverrideState threshold baseStates
  | shortReject : OverrideState threshold baseStates

def OverrideState.equivSum (threshold baseStates : Nat) :
    OverrideState threshold baseStates ≃
      ShortScanData threshold ⊕
        (Fin (threshold + 1) ⊕ (Fin baseStates ⊕ Bool)) where
  toFun
    | .scan data => Sum.inl data
    | .rewind remaining => Sum.inr (Sum.inl remaining)
    | .base state => Sum.inr (Sum.inr (Sum.inl state))
    | .shortAccept => Sum.inr (Sum.inr (Sum.inr true))
    | .shortReject => Sum.inr (Sum.inr (Sum.inr false))
  invFun
    | Sum.inl data => .scan data
    | Sum.inr (Sum.inl remaining) => .rewind remaining
    | Sum.inr (Sum.inr (Sum.inl state)) => .base state
    | Sum.inr (Sum.inr (Sum.inr true)) => .shortAccept
    | Sum.inr (Sum.inr (Sum.inr false)) => .shortReject
  left_inv state := by cases state <;> rfl
  right_inv value := by
    rcases value with data | remainingOrBase
    · rfl
    · rcases remainingOrBase with remaining | baseOrResult
      · rfl
      · rcases baseOrResult with state | result
        · rfl
        · cases result <;> rfl

noncomputable instance (threshold baseStates : Nat) :
    Fintype (OverrideState threshold baseStates) :=
  Fintype.ofEquiv
    (ShortScanData threshold ⊕
      (Fin (threshold + 1) ⊕ (Fin baseStates ⊕ Bool)))
    (OverrideState.equivSum threshold baseStates).symm

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

def finPred {n : Nat} (i : Fin (n + 1))
    (hi : i.val ≠ 0) : Fin (n + 1) :=
  ⟨i.val - 1, (Nat.sub_le i.val 1).trans_lt i.isLt⟩

noncomputable def finiteOverrideTypedMachine
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates) :
    TypedMachine (tapes + 1)
      (OverrideState threshold baseStates) := by
  classical
  exact
    { start :=
        if threshold = 0 then .base baseMachine.start
        else .scan (shortMachineStartData threshold)
      transition := fun state symbols =>
        match state with
        | .shortAccept => (.shortAccept, preserveAll symbols)
        | .shortReject => (.shortReject, preserveAll symbols)
        | .base baseState =>
            let action := baseMachine.transition baseState symbols
            (.base action.1, action.2)
        | .rewind remaining =>
            if hzero : remaining.val = 0 then
              (.base baseMachine.start, preserveAll symbols)
            else
              (.rewind (finPred remaining hzero),
                moveFirstLeft symbols)
        | .scan data =>
            match symbols (firstTapeIndex tapes) with
            | .blank =>
                if data.length.val < threshold ∧
                    data.toList ∈ shortLanguage then
                  (.shortAccept, preserveAll symbols)
                else
                  (.shortReject, preserveAll symbols)
            | .bit bit =>
                if hlength : data.length.val < threshold then
                  if hmore : data.length.val + 1 < threshold then
                    (.scan (data.push bit hlength),
                      moveFirstRight symbols)
                  else
                    (.rewind data.length, preserveAll symbols)
                else
                  (.shortReject, preserveAll symbols)
      result := fun state =>
        match state with
        | .shortAccept => some true
        | .shortReject => some false
        | .base baseState => baseMachine.result baseState
        | .scan _ => none
        | .rewind _ => none }

theorem Tape.move_right_left_custom_of_right_ne_nil
    (tape : Tape) (hright : tape.right ≠ []) :
    Tape.move (Tape.move tape .right) .left = tape := by
  cases tape with
  | mk left head right =>
      cases right with
      | nil => contradiction
      | cons next rest => rfl

theorem Tape.iterate_move_right_right
    (tape : Tape) (steps : Nat) :
    (((Tape.move · .right)^[steps]) tape).right =
      (tape.head :: tape.right).drop (steps + 1) := by
  induction steps generalizing tape with
  | zero => simp
  | succ steps ih =>
      rw [Function.iterate_succ_apply]
      rw [ih]
      cases tape with
      | mk left head right =>
          cases right <;> simp [Tape.move, List.drop_succ_cons]

theorem Tape.iterate_move_right_left_custom
    (bits : List Bool) (steps : Nat)
    (hsteps : steps < bits.length) :
    ((Tape.move · .left)^[steps])
        (((Tape.move · .right)^[steps]) (Tape.ofBits bits)) =
      Tape.ofBits bits := by
  induction steps with
  | zero => rfl
  | succ steps ih =>
      rw [Function.iterate_succ_apply,
        Function.iterate_succ_apply']
      let current :=
        ((Tape.move · .right)^[steps]) (Tape.ofBits bits)
      have hright :
          current.right ≠ [] := by
        rw [show current.right =
            ((Tape.ofBits bits).head ::
              (Tape.ofBits bits).right).drop (steps + 1) by
          exact Tape.iterate_move_right_right
            (Tape.ofBits bits) steps]
        cases bits with
        | nil => simp at hsteps
        | cons first rest =>
            simp only [Tape.ofBits]
            have hs : steps < rest.length := by
              simpa using hsteps
            rw [List.ne_nil_iff_length_pos, List.length_drop]
            simp only [List.length_cons, List.length_map]
            omega
      have hcancel :
          Tape.move (Tape.move current .right) .left =
            current :=
        Tape.move_right_left_custom_of_right_ne_nil
          current hright
      rw [hcancel]
      exact ih (Nat.lt_of_succ_lt hsteps)

def moveOnlyFirstRight {tapes State : Nat}
    (configuration : Configuration (tapes + 1) State) :
    Fin (tapes + 1) → Tape :=
  fun i =>
    if i = firstTapeIndex tapes then
      Tape.move (configuration.tape i) .right
    else
      configuration.tape i

def typedMoveOnlyFirstRight {tapes : Nat} {State : Type}
    (configuration : TypedConfiguration (tapes + 1) State) :
    Fin (tapes + 1) → Tape :=
  fun i =>
    if i = firstTapeIndex tapes then
      Tape.move (configuration.tape i) .right
    else
      configuration.tape i

def typedMoveOnlyFirstLeft {tapes : Nat} {State : Type}
    (configuration : TypedConfiguration (tapes + 1) State) :
    Fin (tapes + 1) → Tape :=
  fun i =>
    if i = firstTapeIndex tapes then
      Tape.move (configuration.tape i) .left
    else
      configuration.tape i

theorem finiteOverrideTypedMachine_step_scan_more
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (configuration :
      TypedConfiguration (tapes + 1)
        (OverrideState threshold baseStates))
    (data : ShortScanData threshold) (bit : Bool)
    (hstate : configuration.state = .scan data)
    (hhead :
      (configuration.tape (firstTapeIndex tapes)).head = .bit bit)
    (hlength : data.length.val < threshold)
    (hmore : data.length.val + 1 < threshold) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        configuration =
      ⟨.scan (data.push bit hlength),
        typedMoveOnlyFirstRight configuration⟩ := by
  unfold TypedMachine.step
  rw [hstate]
  simp only [finiteOverrideTypedMachine]
  rw [hhead]
  simp only
  simp only [dif_pos hlength, dif_pos hmore]
  congr 1
  funext i
  simp only [typedMoveOnlyFirstRight, moveFirstRight]
  by_cases hi : i = firstTapeIndex tapes
  · subst i
    simp [firstTapeIndex, Tape.write_head_eq]
  · have hival : i.val ≠ 0 := by
      intro hzero
      apply hi
      apply Fin.ext
      simpa [firstTapeIndex] using hzero
    simp [hi, hival, Tape.write_head_eq, Tape.move]

theorem finiteOverrideTypedMachine_step_scan_last
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (configuration :
      TypedConfiguration (tapes + 1)
        (OverrideState threshold baseStates))
    (data : ShortScanData threshold) (bit : Bool)
    (hstate : configuration.state = .scan data)
    (hhead :
      (configuration.tape (firstTapeIndex tapes)).head = .bit bit)
    (hlength : data.length.val < threshold)
    (hlast : ¬data.length.val + 1 < threshold) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        configuration =
      ⟨.rewind data.length, configuration.tape⟩ := by
  unfold TypedMachine.step
  rw [hstate]
  simp only [finiteOverrideTypedMachine]
  rw [hhead]
  simp only
  simp only [dif_pos hlength, dif_neg hlast]
  congr 1

theorem finiteOverrideTypedMachine_step_scan_blank_accept
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (configuration :
      TypedConfiguration (tapes + 1)
        (OverrideState threshold baseStates))
    (data : ShortScanData threshold)
    (hstate : configuration.state = .scan data)
    (hhead :
      (configuration.tape (firstTapeIndex tapes)).head = .blank)
    (hcondition :
      data.length.val < threshold ∧
        data.toList ∈ shortLanguage) :
    ((finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        configuration).state = OverrideState.shortAccept := by
  classical
  unfold TypedMachine.step
  rw [hstate]
  simp only [finiteOverrideTypedMachine]
  rw [hhead]
  simp [hcondition]

theorem finiteOverrideTypedMachine_step_scan_blank_reject
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (configuration :
      TypedConfiguration (tapes + 1)
        (OverrideState threshold baseStates))
    (data : ShortScanData threshold)
    (hstate : configuration.state = .scan data)
    (hhead :
      (configuration.tape (firstTapeIndex tapes)).head = .blank)
    (hcondition :
      ¬(data.length.val < threshold ∧
        data.toList ∈ shortLanguage)) :
    ((finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        configuration).state = OverrideState.shortReject := by
  classical
  unfold TypedMachine.step
  rw [hstate]
  simp only [finiteOverrideTypedMachine]
  rw [hhead]
  simp [hcondition]

theorem TypedMachine.run_add {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool) (first extra : Nat) :
    machine.run input (first + extra) =
      (machine.step^[extra]) (machine.run input first) := by
  induction extra with
  | zero => simp
  | succ extra ih =>
      rw [Nat.add_succ, TypedMachine.run, ih]
      rw [Function.iterate_succ_apply']

def tapesAfterFirstRight {tapes : Nat}
    (input : Fin (tapes + 1) → List Bool)
    (steps : Nat) : Fin (tapes + 1) → Tape :=
  fun i =>
    if i = firstTapeIndex tapes then
      ((Tape.move · .right)^[steps]) (Tape.ofBits (input i))
    else
      Tape.ofBits (input i)

theorem ShortScanData.ofList_congr {threshold : Nat}
    {bits₁ bits₂ : List Bool}
    (hbits : bits₁ = bits₂)
    (h₁ : bits₁.length ≤ threshold)
    (h₂ : bits₂.length ≤ threshold) :
    ShortScanData.ofList bits₁ h₁ =
      ShortScanData.ofList bits₂ h₂ := by
  subst bits₂
  rfl

theorem finiteOverrideTypedMachine_run_scan
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (input : Fin (tapes + 1) → List Bool)
    (steps : Nat)
    (hthreshold : steps < threshold)
    (hinput : steps ≤ (input (firstTapeIndex tapes)).length) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).run
        input steps =
      ⟨.scan
          (ShortScanData.ofList
            ((input (firstTapeIndex tapes)).take steps)
            ((List.length_take_le _ _).trans
              (Nat.le_of_lt hthreshold))),
        tapesAfterFirstRight input steps⟩ := by
  induction steps with
  | zero =>
      simp only [TypedMachine.run, TypedMachine.initialConfiguration,
        finiteOverrideTypedMachine, hthreshold.ne', if_false,
        tapesAfterFirstRight, Function.iterate_zero_apply,
        ShortScanData.ofList, List.take_zero, List.length_nil]
      congr 1
      funext i
      simp [tapesAfterFirstRight]
  | succ steps ih =>
      have hstepsThreshold : steps < threshold :=
        (Nat.lt_succ_self steps).trans hthreshold
      have hstepsInput :
          steps < (input (firstTapeIndex tapes)).length :=
        Nat.lt_of_succ_le hinput
      have ih' :=
        ih hstepsThreshold
          (Nat.le_of_lt hstepsInput)
      rw [TypedMachine.run, ih']
      have hhead :
          (tapesAfterFirstRight input steps
              (firstTapeIndex tapes)).head =
            .bit
              (input (firstTapeIndex tapes))[steps] := by
        simp only [tapesAfterFirstRight, if_pos]
        exact
          Tape.iterate_move_right_ofBits_head_of_lt
            (input (firstTapeIndex tapes)) hstepsInput
      let scanned :=
        (input (firstTapeIndex tapes)).take steps
      have hscannedLength :
          scanned.length = steps :=
        List.length_take_of_le (Nat.le_of_lt hstepsInput)
      have hdataLength :
          (ShortScanData.ofList scanned
            ((List.length_take_le _ _).trans
              (Nat.le_of_lt hstepsThreshold))).length.val <
              threshold := by
        change scanned.length < threshold
        rw [hscannedLength]
        exact hstepsThreshold
      have hmore :
          (ShortScanData.ofList scanned
              ((List.length_take_le _ _).trans
                (Nat.le_of_lt hstepsThreshold))).length.val + 1 <
            threshold := by
        change scanned.length + 1 < threshold
        rw [hscannedLength]
        exact hthreshold
      rw [finiteOverrideTypedMachine_step_scan_more
        shortLanguage threshold baseMachine
        ⟨.scan
          (ShortScanData.ofList scanned
            ((List.length_take_le _ _).trans
              (Nat.le_of_lt hstepsThreshold))),
          tapesAfterFirstRight input steps⟩
        _ _ rfl hhead hdataLength hmore]
      congr 1
      · congr 2
        have hpush :=
          ShortScanData.push_ofList scanned
            (by simpa [hscannedLength] using hstepsThreshold)
            (input (firstTapeIndex tapes))[steps]
        have htake :
            (input (firstTapeIndex tapes)).take (steps + 1) =
              scanned ++
                [(input (firstTapeIndex tapes))[steps]] := by
          simpa [scanned] using
            List.take_succ_eq_append_getElem hstepsInput
        calc
          (ShortScanData.ofList scanned
              ((List.length_take_le _ _).trans
                (Nat.le_of_lt hstepsThreshold))).push
                (input (firstTapeIndex tapes))[steps] hdataLength
              =
            (ShortScanData.ofList scanned
              (Nat.le_of_lt
                (by simpa [hscannedLength] using hstepsThreshold))).push
                (input (firstTapeIndex tapes))[steps]
                (by
                  change scanned.length < threshold
                  rw [hscannedLength]
                  exact hstepsThreshold) := by
                  congr
          _ =
            ShortScanData.ofList
              (scanned ++
                [(input (firstTapeIndex tapes))[steps]])
              (by
                simpa [hscannedLength] using
                  Nat.succ_le_of_lt hstepsThreshold) := hpush
          _ =
            ShortScanData.ofList
              ((input (firstTapeIndex tapes)).take (steps + 1))
              ((List.length_take_le _ _).trans
                (Nat.le_of_lt hthreshold)) :=
            ShortScanData.ofList_congr htake.symm _ _
      · funext i
        simp only [typedMoveOnlyFirstRight,
          tapesAfterFirstRight]
        by_cases hi : i = firstTapeIndex tapes
        · subst i
          simp only [if_pos]
          rw [Function.iterate_succ_apply']
        · simp only [hi, if_false]

theorem finiteOverrideTypedMachine_step_rewind_zero
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (configuration :
      TypedConfiguration (tapes + 1)
        (OverrideState threshold baseStates))
    (remaining : Fin (threshold + 1))
    (hstate : configuration.state = .rewind remaining)
    (hzero : remaining.val = 0) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        configuration =
      ⟨.base baseMachine.start, configuration.tape⟩ := by
  unfold TypedMachine.step
  rw [hstate]
  simp only [finiteOverrideTypedMachine]
  simp only [dif_pos hzero]
  congr 1

theorem finiteOverrideTypedMachine_step_rewind_succ
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (configuration :
      TypedConfiguration (tapes + 1)
        (OverrideState threshold baseStates))
    (remaining : Fin (threshold + 1))
    (hstate : configuration.state = .rewind remaining)
    (hnonzero : remaining.val ≠ 0) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        configuration =
      ⟨.rewind (finPred remaining hnonzero),
        typedMoveOnlyFirstLeft configuration⟩ := by
  unfold TypedMachine.step
  rw [hstate]
  simp only [finiteOverrideTypedMachine]
  simp only [dif_neg hnonzero]
  congr 1
  funext i
  simp only [typedMoveOnlyFirstLeft, moveFirstLeft]
  by_cases hi : i = firstTapeIndex tapes
  · subst i
    simp [firstTapeIndex, Tape.write_head_eq]
  · have hival : i.val ≠ 0 := by
      intro hzero
      apply hi
      apply Fin.ext
      simpa [firstTapeIndex] using hzero
    simp [hi, hival, Tape.write_head_eq, Tape.move]

theorem finiteOverrideTypedMachine_iterate_rewind
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (configuration :
      TypedConfiguration (tapes + 1)
        (OverrideState threshold baseStates))
    (remaining : Fin (threshold + 1))
    (hstate : configuration.state = .rewind remaining) :
    ((finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        ^[remaining.val + 1]) configuration =
      ⟨.base baseMachine.start,
        fun i =>
          if i = firstTapeIndex tapes then
            ((Tape.move · .left)^[remaining.val])
              (configuration.tape i)
          else
            configuration.tape i⟩ := by
  induction hvalue : remaining.val using Nat.strong_induction_on
      generalizing configuration remaining with
  | h value ih =>
      by_cases hzero : remaining.val = 0
      · have hvalueZero : value = 0 := by omega
        subst value
        have hexponent : remaining.val + 1 = 1 := by omega
        rw [hexponent, Function.iterate_one]
        simp only [hzero, Function.iterate_zero_apply]
        rw [finiteOverrideTypedMachine_step_rewind_zero
          shortLanguage threshold baseMachine
          configuration remaining hstate hzero]
        congr 1
        funext i
        simp
      · have hpositive : 0 < remaining.val :=
          Nat.pos_of_ne_zero hzero
        have hpredVal :
            (finPred remaining hzero).val =
              remaining.val - 1 := rfl
        rw [Function.iterate_succ_apply]
        have hstep :=
          finiteOverrideTypedMachine_step_rewind_succ
            shortLanguage threshold baseMachine
            configuration remaining hstate hzero
        rw [hstep]
        have ih' :=
          ih (remaining.val - 1)
            (by omega)
            ⟨.rewind (finPred remaining hzero),
              typedMoveOnlyFirstLeft configuration⟩
            (finPred remaining hzero) rfl rfl
        have hvaluePred :
            value = remaining.val - 1 + 1 := by omega
        rw [hvaluePred, ih']
        congr 1
        funext i
        by_cases hi : i = firstTapeIndex tapes
        · subst i
          simp only [if_pos, typedMoveOnlyFirstLeft]
          rw [Function.iterate_succ_apply]
        · simp [hi, typedMoveOnlyFirstLeft]

theorem finiteOverrideTypedMachine_run_enter_base
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (input : Fin (tapes + 1) → List Bool)
    (hlong :
      threshold ≤ (input (firstTapeIndex tapes)).length) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).run
        input (2 * threshold) =
      ⟨.base baseMachine.start,
        fun i => Tape.ofBits (input i)⟩ := by
  cases threshold with
  | zero =>
      simp [finiteOverrideTypedMachine,
        TypedMachine.run, TypedMachine.initialConfiguration]
  | succ steps =>
      have hscan :=
        finiteOverrideTypedMachine_run_scan
          shortLanguage (steps + 1) baseMachine input steps
          (Nat.lt_succ_self steps)
          (by omega)
      let data :=
        ShortScanData.ofList
          ((input (firstTapeIndex tapes)).take steps)
          ((List.length_take_le _ _).trans
            (Nat.le_succ steps))
      have hstepsInput :
          steps < (input (firstTapeIndex tapes)).length := by
        omega
      have hhead :
          (tapesAfterFirstRight input steps
              (firstTapeIndex tapes)).head =
            .bit
              (input (firstTapeIndex tapes))[steps] := by
        simp only [tapesAfterFirstRight, if_pos]
        exact
          Tape.iterate_move_right_ofBits_head_of_lt
            (input (firstTapeIndex tapes)) hstepsInput
      have hdataLength :
          data.length.val < steps + 1 := by
        change
          ((input (firstTapeIndex tapes)).take steps).length <
            steps + 1
        rw [List.length_take_of_le hstepsInput.le]
        omega
      have hlast :
          ¬data.length.val + 1 < steps + 1 := by
        change
          ¬((input (firstTapeIndex tapes)).take steps).length + 1 <
            steps + 1
        rw [List.length_take_of_le hstepsInput.le]
        omega
      have henter :
          (finiteOverrideTypedMachine shortLanguage (steps + 1)
              baseMachine).run input (steps + 1) =
            ⟨.rewind data.length,
              tapesAfterFirstRight input steps⟩ := by
        rw [TypedMachine.run, hscan]
        exact
          finiteOverrideTypedMachine_step_scan_last
            shortLanguage (steps + 1) baseMachine
            ⟨.scan data, tapesAfterFirstRight input steps⟩
            data (input (firstTapeIndex tapes))[steps]
            rfl hhead hdataLength hlast
      have hrewind :=
        finiteOverrideTypedMachine_iterate_rewind
          shortLanguage (steps + 1) baseMachine
          ⟨.rewind data.length,
            tapesAfterFirstRight input steps⟩
          data.length rfl
      have hdataVal : data.length.val = steps := by
        change
          ((input (firstTapeIndex tapes)).take steps).length =
            steps
        exact List.length_take_of_le hstepsInput.le
      have htime :
          2 * (steps + 1) =
            (steps + 1) + (data.length.val + 1) := by
        omega
      rw [htime, TypedMachine.run_add, henter, hrewind]
      congr 1
      funext i
      by_cases hi : i = firstTapeIndex tapes
      · subst i
        simp only [if_pos, tapesAfterFirstRight]
        rw [hdataVal]
        exact
          Tape.iterate_move_right_left_custom
            (input (firstTapeIndex tapes)) steps hstepsInput
      · simp [hi, tapesAfterFirstRight]

def embedBaseConfiguration
    {tapes baseStates threshold : Nat}
    (configuration : Configuration (tapes + 1) baseStates) :
    TypedConfiguration (tapes + 1)
      (OverrideState threshold baseStates) :=
  ⟨.base configuration.state, configuration.tape⟩

theorem finiteOverrideTypedMachine_step_embedBase
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (configuration : Configuration (tapes + 1) baseStates) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        (embedBaseConfiguration
          (threshold := threshold) configuration) =
      embedBaseConfiguration
        (threshold := threshold)
        (baseMachine.step configuration) := by
  cases hresult : baseMachine.result configuration.state with
  | some result =>
      unfold TypedMachine.step Machine.step
      simp [embedBaseConfiguration,
        finiteOverrideTypedMachine, hresult]
  | none =>
      unfold TypedMachine.step Machine.step
      simp [embedBaseConfiguration,
        finiteOverrideTypedMachine, hresult]

theorem finiteOverrideTypedMachine_iterate_embedBase
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (configuration : Configuration (tapes + 1) baseStates)
    (steps : Nat) :
    ((finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        ^[steps])
        (embedBaseConfiguration
          (threshold := threshold) configuration) =
      embedBaseConfiguration
        (threshold := threshold)
        ((baseMachine.step^[steps]) configuration) := by
  induction steps generalizing configuration with
  | zero => rfl
  | succ steps ih =>
      rw [Function.iterate_succ_apply]
      rw [finiteOverrideTypedMachine_step_embedBase]
      rw [Function.iterate_succ_apply]
      exact ih (baseMachine.step configuration)

theorem Machine.run_add {tapes states : Nat}
    (machine : Machine tapes states)
    (input : Fin tapes → List Bool) (first extra : Nat) :
    machine.run input (first + extra) =
      (machine.step^[extra]) (machine.run input first) := by
  induction extra with
  | zero => simp
  | succ extra ih =>
      rw [Nat.add_succ, Machine.run, ih]
      rw [Function.iterate_succ_apply']

theorem finiteOverrideTypedMachine_run_long
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (input : Fin (tapes + 1) → List Bool)
    (hlong :
      threshold ≤ (input (firstTapeIndex tapes)).length)
    (steps : Nat) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).run
        input (2 * threshold + steps) =
      embedBaseConfiguration
        (threshold := threshold)
        (baseMachine.run input steps) := by
  rw [TypedMachine.run_add,
    finiteOverrideTypedMachine_run_enter_base
      shortLanguage threshold baseMachine input hlong]
  change
    ((finiteOverrideTypedMachine shortLanguage threshold baseMachine).step
        ^[steps])
        (embedBaseConfiguration
          (threshold := threshold)
          (SipserGacsLautemann.initialConfiguration
            baseMachine input)) =
      embedBaseConfiguration
        (threshold := threshold)
        (baseMachine.run input steps)
  rw [finiteOverrideTypedMachine_iterate_embedBase]
  congr 1
  simpa [Machine.run] using
    (Machine.run_add baseMachine input 0 steps).symm

theorem finiteOverrideTypedMachine_result_short_early
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (input : Fin (tapes + 1) → List Bool)
    [Decidable
      (input (firstTapeIndex tapes) ∈ shortLanguage)]
    (hshort :
      (input (firstTapeIndex tapes)).length < threshold) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).result
        ((finiteOverrideTypedMachine shortLanguage threshold baseMachine).run
          input
          ((input (firstTapeIndex tapes)).length + 1)).state =
      some
        (decide
          (input (firstTapeIndex tapes) ∈ shortLanguage)) := by
  classical
  let length :=
    (input (firstTapeIndex tapes)).length
  have hscan :=
    finiteOverrideTypedMachine_run_scan
      shortLanguage threshold baseMachine input length
      hshort le_rfl
  let data :=
    ShortScanData.ofList
      ((input (firstTapeIndex tapes)).take length)
      ((List.length_take_le _ _).trans hshort.le)
  have hhead :
      (tapesAfterFirstRight input length
          (firstTapeIndex tapes)).head = .blank := by
    simp only [tapesAfterFirstRight, if_pos]
    exact
      Tape.iterate_move_right_ofBits_head_length
        (input (firstTapeIndex tapes))
  have hdataList :
      data.toList = input (firstTapeIndex tapes) := by
    dsimp [data]
    rw [ShortScanData.toList_ofList]
    exact List.take_length
  have hdataLength :
      data.length.val < threshold := by
    change
      ((input (firstTapeIndex tapes)).take length).length <
        threshold
    rw [List.take_length]
    exact hshort
  rw [TypedMachine.run, hscan]
  by_cases hmember :
      input (firstTapeIndex tapes) ∈ shortLanguage
  · have hstep :=
      finiteOverrideTypedMachine_step_scan_blank_accept
        shortLanguage threshold baseMachine
        ⟨.scan data, tapesAfterFirstRight input length⟩
        data rfl hhead
        ⟨hdataLength, by simpa [hdataList]⟩
    rw [hstep]
    simp [finiteOverrideTypedMachine, hmember]
  · have hstep :=
      finiteOverrideTypedMachine_step_scan_blank_reject
        shortLanguage threshold baseMachine
        ⟨.scan data, tapesAfterFirstRight input length⟩
        data rfl hhead
        (by simp [hdataList, hmember])
    rw [hstep]
    simp [finiteOverrideTypedMachine, hmember]

theorem finiteOverrideTypedMachine_result_short
    {tapes baseStates : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (baseMachine : Machine (tapes + 1) baseStates)
    (input : Fin (tapes + 1) → List Bool)
    [Decidable
      (input (firstTapeIndex tapes) ∈ shortLanguage)]
    (hshort :
      (input (firstTapeIndex tapes)).length < threshold)
    (totalSteps : Nat)
    (htotal :
      (input (firstTapeIndex tapes)).length + 1 ≤ totalSteps) :
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine).result
        ((finiteOverrideTypedMachine shortLanguage threshold baseMachine).run
          input totalSteps).state =
      some
        (decide
          (input (firstTapeIndex tapes) ∈ shortLanguage)) := by
  obtain ⟨extra, rfl⟩ :=
    Nat.exists_eq_add_of_le htotal
  have hearly :=
    finiteOverrideTypedMachine_result_short_early
      shortLanguage threshold baseMachine input hshort
  have hrun :=
    (finiteOverrideTypedMachine shortLanguage threshold baseMachine
      ).run_add_eq_of_result_run_eq_some
      input
      ((input (firstTapeIndex tapes)).length + 1)
      extra hearly
  rw [hrun]
  exact hearly

theorem polynomiallyBounded_add_constant
    {time : Nat → Nat} (constant : Nat)
    (htime : PolynomiallyBounded time) :
    PolynomiallyBounded (fun n => constant + time n) := by
  rcases htime with ⟨coefficient, degree, hbound⟩
  refine ⟨constant + coefficient, degree, ?_⟩
  intro n
  have hpower : 1 ≤ (n + 1) ^ degree :=
    Nat.one_le_pow degree (n + 1) (Nat.succ_pos n)
  have hconstant :
      constant ≤ constant * (n + 1) ^ degree := by
    simpa using Nat.mul_le_mul_left constant hpower
  calc
    constant + time n ≤
        constant * (n + 1) ^ degree +
          coefficient * (n + 1) ^ degree := by
      exact Nat.add_le_add hconstant (hbound n)
    _ = (constant + coefficient) *
          (n + 1) ^ degree := by
      rw [Nat.add_mul]

theorem decidesInPolynomialTime_finiteOverride
    {tapes : Nat}
    (shortLanguage : Language) (threshold : Nat)
    (basePredicate :
      (Fin (tapes + 1) → List Bool) → Prop)
    (hbase : DecidesInPolynomialTime basePredicate) :
    DecidesInPolynomialTime
      (fun input : Fin (tapes + 1) → List Bool =>
        if (input (firstTapeIndex tapes)).length < threshold then
          input (firstTapeIndex tapes) ∈ shortLanguage
        else
          basePredicate input) := by
  classical
  rcases hbase with
    ⟨baseStates, baseMachine, baseTime,
      hbaseTime, hbaseCorrect⟩
  let typedMachine :=
    finiteOverrideTypedMachine
      shortLanguage threshold baseMachine
  let machine := typedMachine.toMachine
  let time : Nat → Nat :=
    fun n => 2 * threshold + baseTime n
  refine
    ⟨Fintype.card (OverrideState threshold baseStates),
      machine, time,
      polynomiallyBounded_add_constant
        (2 * threshold) hbaseTime,
      ?_⟩
  intro input
  let totalLength := totalInputLength input
  let baseSteps := baseTime totalLength
  by_cases hshort :
      (input (firstTapeIndex tapes)).length < threshold
  · have htotal :
        (input (firstTapeIndex tapes)).length + 1 ≤
          2 * threshold + baseSteps := by
      omega
    letI :
        Decidable
          (input (firstTapeIndex tapes) ∈ shortLanguage) :=
      Classical.propDecidable _
    have hresult :=
      finiteOverrideTypedMachine_result_short
        shortLanguage threshold baseMachine input
        hshort (2 * threshold + baseSteps) htotal
    constructor
    · rw [typedMachine.toMachine_acceptsWithin_iff]
      simpa [typedMachine, machine, time, baseSteps,
        totalLength, hshort] using
        (show
          typedMachine.result
              (typedMachine.run input
                (2 * threshold + baseSteps)).state =
                some true ↔
            input (firstTapeIndex tapes) ∈ shortLanguage by
          rw [hresult]
          simp)
    · rw [typedMachine.toMachine_rejectsWithin_iff]
      simpa [typedMachine, machine, time, baseSteps,
        totalLength, hshort] using
        (show
          typedMachine.result
              (typedMachine.run input
                (2 * threshold + baseSteps)).state =
                some false ↔
            ¬input (firstTapeIndex tapes) ∈ shortLanguage by
          rw [hresult]
          simp)
  · have hlong :
        threshold ≤
          (input (firstTapeIndex tapes)).length :=
      Nat.le_of_not_gt hshort
    have hrun :=
      finiteOverrideTypedMachine_run_long
        shortLanguage threshold baseMachine input
        hlong baseSteps
    have hbaseInput := hbaseCorrect input
    constructor
    · rw [typedMachine.toMachine_acceptsWithin_iff]
      change
        typedMachine.result
            (typedMachine.run input
              (2 * threshold + baseSteps)).state =
              some true ↔
          (if
            (input (firstTapeIndex tapes)).length < threshold
           then input (firstTapeIndex tapes) ∈ shortLanguage
           else basePredicate input)
      rw [hrun]
      change
        baseMachine.result
            (baseMachine.run input baseSteps).state =
              some true ↔ _
      simpa [hshort, Machine.acceptsWithin,
        baseSteps, totalLength] using hbaseInput.1
    · rw [typedMachine.toMachine_rejectsWithin_iff]
      change
        typedMachine.result
            (typedMachine.run input
              (2 * threshold + baseSteps)).state =
              some false ↔
          ¬(if
            (input (firstTapeIndex tapes)).length < threshold
           then input (firstTapeIndex tapes) ∈ shortLanguage
           else basePredicate input)
      rw [hrun]
      change
        baseMachine.result
            (baseMachine.run input baseSteps).state =
              some false ↔ _
      simpa [hshort, Machine.rejectsWithin,
        baseSteps, totalLength] using hbaseInput.2

theorem DecidesInPolynomialTime.congr
    {tapes : Nat}
    {predicate₁ predicate₂ :
      (Fin tapes → List Bool) → Prop}
    (hdecides : DecidesInPolynomialTime predicate₁)
    (hequiv : ∀ input, predicate₁ input ↔ predicate₂ input) :
    DecidesInPolynomialTime predicate₂ := by
  rcases hdecides with
    ⟨states, machine, time, htime, hcorrect⟩
  refine ⟨states, machine, time, htime, ?_⟩
  intro input
  constructor
  · exact (hcorrect input).1.trans (hequiv input)
  · exact (hcorrect input).2.trans (not_congr (hequiv input))

end SipserGacsLautemann
Source
Reusable finite-exception closure 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