Package polynomial-time deciders as typed result machines
Definitionsgl_dpt_to_result_machinecomplexity-theoryleansipser-gacs-lautemannturing-machines
This module converts between the mission’s raw finite-state machine model and the typed-machine interface. It defines Machine.toTypedMachine, proves that it preserves initial configurations, steps, runs, and results, and then packages any DecidesInPolynomialTime proof as a finite typed machine whose final result is exactly some (decide (P input)) at the same polynomial clock.
This is the converse interface to sgl_result_machine_dpt: together, the two modules let scheduler proofs move cleanly between Boolean-result machines and the standard polynomial-time decidability predicate.
Definition code
import Definitions.Def_sgl_machine_infrastructure
namespace SipserGacsLautemann
def Machine.toTypedMachine {tapes states : Nat}
(machine : Machine tapes states) :
TypedMachine tapes (Fin states) where
start := machine.start
transition := machine.transition
result := machine.result
theorem Machine.toTypedMachine_initialConfiguration
{tapes states : Nat}
(machine : Machine tapes states)
(input : Fin tapes → List Bool) :
machine.toTypedMachine.initialConfiguration input =
{ state := (initialConfiguration machine input).state
tape := (initialConfiguration machine input).tape } := by
rfl
theorem Machine.toTypedMachine_step
{tapes states : Nat}
(machine : Machine tapes states)
(configuration : Configuration tapes states) :
machine.toTypedMachine.step
{ state := configuration.state
tape := configuration.tape } =
{ state := (machine.step configuration).state
tape := (machine.step configuration).tape } := by
cases hresult : machine.result configuration.state with
| none =>
simp [Machine.toTypedMachine, TypedMachine.step,
Machine.step, hresult]
| some result =>
simp [Machine.toTypedMachine, TypedMachine.step,
Machine.step, hresult]
theorem Machine.toTypedMachine_run
{tapes states : Nat}
(machine : Machine tapes states)
(input : Fin tapes → List Bool)
(steps : Nat) :
machine.toTypedMachine.run input steps =
{ state := (machine.run input steps).state
tape := (machine.run input steps).tape } := by
induction steps with
| zero =>
rfl
| succ steps ih =>
rw [TypedMachine.run, Machine.run, ih]
exact machine.toTypedMachine_step (machine.run input steps)
theorem Machine.toTypedMachine_result_run
{tapes states : Nat}
(machine : Machine tapes states)
(input : Fin tapes → List Bool)
(steps : Nat) :
machine.toTypedMachine.result
(machine.toTypedMachine.run input steps).state =
machine.result (machine.run input steps).state := by
rw [machine.toTypedMachine_run]
rfl
theorem DecidesInPolynomialTime.to_typed_result_decide
{tapes : Nat}
{predicate : (Fin tapes → List Bool) → Prop}
[DecidablePred predicate]
(hdecides : DecidesInPolynomialTime predicate) :
∃ (State : Type) (_ : Fintype State)
(machine : TypedMachine tapes State)
(time : Nat → Nat),
PolynomiallyBounded time ∧
∀ input : Fin tapes → List Bool,
machine.result
(machine.run input
(time (totalInputLength input))).state =
some (decide (predicate input)) := by
classical
rcases hdecides with
⟨states, machine, time, htime, hcorrect⟩
refine
⟨Fin states, inferInstance, machine.toTypedMachine,
time, htime, ?_⟩
intro input
rw [machine.toTypedMachine_result_run]
by_cases hp : predicate input
· have haccept :
machine.acceptsWithin input
(time (totalInputLength input)) :=
(hcorrect input).1.mpr hp
simpa [Machine.acceptsWithin, hp] using haccept
· have hreject :
machine.rejectsWithin input
(time (totalInputLength input)) :=
(hcorrect input).2.mpr hp
simpa [Machine.rejectsWithin, hp] using hreject
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission finite typed-machine infrastructure.