Encoded simulator readout for relabeled machines
Definitionsgl_encoded_to_machine_adapterscomplexity-theorysipser-gacs-lautemannturing-machines
This module converts the published typed encoded-simulator correctness theorem into statements about the ordinary mission Machine obtained from the simulator by finite-state relabeling. If the simulator is run on tapes containing encodeInputBits of a logical input for 6 * t steps, then its resulting state has exactly the same accept/reject result as the base machine run on the logical input for t steps. It also provides accept-within and reject-within equivalences.
This packages the verifier-execution phase needed by the remaining Sipser--Gács--Lautemann scheduler proof: once a loader has written encoded query tapes, the existing encoded simulator can be used as an ordinary finite-state machine with the expected result.
Definition code
import Definitions.Def_sgl_encoded_simulator
namespace SipserGacsLautemann
theorem encodedSimulation_toMachine_result_run_encoded
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(input : Fin tapes → List Bool)
(steps : Nat) :
(encodedSimulationTypedMachine baseMachine).toMachine.result
(((encodedSimulationTypedMachine baseMachine).toMachine).run
(fun i => encodeInputBits (input i))
(6 * steps)).state =
baseMachine.result
(baseMachine.run input steps).state := by
rw [TypedMachine.toMachine_run_encode]
simp [TypedConfiguration.encode, TypedMachine.toMachine]
exact encodedSimulation_result_run_encoded
baseMachine input steps
theorem encodedSimulation_toMachine_acceptsWithin_encoded
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(input : Fin tapes → List Bool)
(steps : Nat) :
((encodedSimulationTypedMachine baseMachine).toMachine
).acceptsWithin
(fun i => encodeInputBits (input i)) (6 * steps) ↔
baseMachine.acceptsWithin input steps := by
unfold Machine.acceptsWithin
rw [encodedSimulation_toMachine_result_run_encoded]
theorem encodedSimulation_toMachine_rejectsWithin_encoded
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(input : Fin tapes → List Bool)
(steps : Nat) :
((encodedSimulationTypedMachine baseMachine).toMachine
).rejectsWithin
(fun i => encodeInputBits (input i)) (6 * steps) ↔
baseMachine.rejectsWithin input steps := by
unfold Machine.rejectsWithin
rw [encodedSimulation_toMachine_result_run_encoded]
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; adapter around the published encoded simulator correctness theorem.