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