SGL simulator reachability and result adapters
Definitionsgl_simulation_result_adapterscomplexity-theorysipser-gacs-lautemannturing-machines
This module packages result-readout and reachability adapters for the Sipser--Gács--Lautemann simulator stack. It lifts ReachesWithin proofs through the move-left prefix when the prefixed machine is already in an embedded running state, records that embedded prefixed states have the same result as the underlying typed machine, and records that a completed left-zigzag simulation reads out exactly the result of the simulated base machine run.
These lemmas are intended for the remaining aggregation scheduler: after a loader constructs a ready verifier-query configuration, these adapters let the proof append the verifier simulation phase and recover the Boolean answer with the published polynomial-overhead bound.
Definition code
import Definitions.Def_sgl_move_left_prefix_reaches
namespace SipserGacsLautemann
theorem moveLeftPrefixTypedMachine_iterate_embedded
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(configuration : TypedConfiguration tapes State)
(steps : Nat) :
((moveLeftPrefixTypedMachine machine).step^[steps])
(MoveLeftPrefixState.embedConfiguration configuration) =
MoveLeftPrefixState.embedConfiguration
((machine.step^[steps]) configuration) := by
induction steps with
| zero => rfl
| succ steps ih =>
rw [Function.iterate_succ_apply',
Function.iterate_succ_apply', ih]
exact moveLeftPrefixTypedMachine_step_running
machine ((machine.step^[steps]) configuration)
theorem moveLeftPrefixTypedMachine_reaches_embedded
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
{initial final : TypedConfiguration tapes State}
{bound : Nat}
(hreaches :
ReachesWithin machine.step initial final bound) :
ReachesWithin
(moveLeftPrefixTypedMachine machine).step
(MoveLeftPrefixState.embedConfiguration initial)
(MoveLeftPrefixState.embedConfiguration final)
bound := by
rcases hreaches with ⟨steps, hle, hsteps⟩
refine ⟨steps, hle, ?_⟩
rw [moveLeftPrefixTypedMachine_iterate_embedded, hsteps]
theorem moveLeftPrefixTypedMachine_result_embedded
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(configuration : TypedConfiguration tapes State) :
(moveLeftPrefixTypedMachine machine).result
(MoveLeftPrefixState.embedConfiguration configuration).state =
machine.result configuration.state := by
rfl
theorem leftZigzagReadyConfiguration_result
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(configuration : Configuration 2 baseStates)
(archives : Fin 2 → List TapeSymbol)
(positions : Fin 2 → Int)
(recordCount : Nat) :
(leftZigzagSimulationTypedMachine baseMachine).result
(leftZigzagReadyConfiguration
configuration archives positions recordCount).state =
baseMachine.result configuration.state := by
rfl
theorem leftZigzagSimulation_reaches_run_with_result
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(input : Fin 2 → List Bool)
(archives : Fin 2 → List TapeSymbol)
(steps horizon : Nat)
(hsteps : steps ≤ horizon) :
∃ final : TypedConfiguration 2
(ZigzagSimulationState baseStates),
ReachesWithin
(leftZigzagSimulationTypedMachine baseMachine).step
(leftZigzagReadyConfiguration
(baseMachine.run input 0) archives
(zigzagRunPositions baseMachine input 0)
(2 * horizon + 3))
final
(steps * (24 * horizon + 32)) ∧
(leftZigzagSimulationTypedMachine baseMachine).result
final.state =
baseMachine.result
(baseMachine.run input steps).state := by
refine
⟨leftZigzagReadyConfiguration
(baseMachine.run input steps) archives
(zigzagRunPositions baseMachine input steps)
(2 * horizon + 3),
leftZigzagSimulation_reaches_run
baseMachine input archives steps horizon hsteps,
?_⟩
exact
leftZigzagReadyConfiguration_result
baseMachine (baseMachine.run input steps)
archives (zigzagRunPositions baseMachine input steps)
(2 * horizon + 3)
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; deterministic Turing-machine simulator bookkeeping for the shared aggregation scheduler.