sgl_finite_override
Definitioncomplexity-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 SipserGacsLautemannSource
Reusable finite-exception construction for the custom Turing-machine model in the Sipser–Gács–Lautemann mission.