SGL mirrored zigzag global correctness, packaged
Definitionsgl_left_zigzag_global_packagedcomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module derives the mirrored, right-archive version of the global zigzag simulator, using only server-visible Definitions.Def_* imports. It is useful for schedulers that begin from the mission machine initial tape layout, where raw input can be preserved on the right side of a blank head while encoded work is maintained on the left.
Definition code
import Definitions.Def_sgl_zigzag_global
namespace SipserGacsLautemann
def leftZigzagReadyConfiguration
{baseStates : Nat}
(configuration : Configuration 2 baseStates)
(archives : Fin 2 → List TapeSymbol)
(positions : Fin 2 → Int)
(recordCount : Nat) :
TypedConfiguration 2
(ZigzagSimulationState baseStates) :=
mirrorTypedConfiguration
(zigzagReadyConfiguration configuration archives
positions recordCount)
theorem mirrorTypedMachine_iterate_step
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(configuration : TypedConfiguration tapes State)
(steps : Nat) :
((mirrorTypedMachine machine).step^[steps])
(mirrorTypedConfiguration configuration) =
mirrorTypedConfiguration
((machine.step^[steps]) configuration) := by
induction steps generalizing configuration with
| zero => rfl
| succ steps ih =>
rw [Function.iterate_succ_apply',
Function.iterate_succ_apply', ih]
exact mirrorTypedMachine_step machine
((machine.step^[steps]) configuration)
theorem ReachesWithin.mirrorTypedMachine
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
{initial final : TypedConfiguration tapes State}
{bound : Nat}
(hreaches :
ReachesWithin machine.step initial final bound) :
ReachesWithin (mirrorTypedMachine machine).step
(mirrorTypedConfiguration initial)
(mirrorTypedConfiguration final) bound := by
rcases hreaches with ⟨steps, hle, hsteps⟩
refine ⟨steps, hle, ?_⟩
rw [mirrorTypedMachine_iterate_step, hsteps]
theorem leftZigzagSimulation_reaches_run
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(input : Fin 2 → List Bool)
(archives : Fin 2 → List TapeSymbol)
(steps horizon : Nat)
(hsteps : steps ≤ horizon) :
ReachesWithin
(leftZigzagSimulationTypedMachine baseMachine).step
(leftZigzagReadyConfiguration
(baseMachine.run input 0) archives
(zigzagRunPositions baseMachine input 0)
(2 * horizon + 3))
(leftZigzagReadyConfiguration
(baseMachine.run input steps) archives
(zigzagRunPositions baseMachine input steps)
(2 * horizon + 3))
(steps * (24 * horizon + 32)) := by
exact
(zigzagSimulation_reaches_run
baseMachine input archives steps horizon hsteps
).mirrorTypedMachine (zigzagSimulationTypedMachine baseMachine)
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.