SGL raw archive empty simulator start
Definitionsgl_raw_archive_empty_runcomplexity-theorysipser-gacs-lautemannturing-machines
This module records the exact zero-record start layout obtained when the move-left prefix is applied to the left-zigzag simulator. From ordinary two-tape raw input, one prefix step reaches the embedded left-zigzag ready configuration whose virtual verifier tapes are empty and whose archive component contains the original raw input bits. This isolates the remaining scheduler work: padding the work-record area and loading derived verifier queries from the archive.
Definition code
import Definitions.Def_sgl_move_left_prefix_reaches
namespace SipserGacsLautemann
theorem moveLeftInitialConfiguration_leftZigzag_empty_archive
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(input : Fin 2 → List Bool) :
moveLeftInitialConfiguration
(leftZigzagSimulationTypedMachine baseMachine) input =
leftZigzagReadyConfiguration
(initialConfiguration baseMachine (fun _ : Fin 2 => []))
(fun i : Fin 2 => rawArchiveSymbols (input i))
(fun _ : Fin 2 => 0) 0 := by
simp only [moveLeftInitialConfiguration,
leftZigzagReadyConfiguration,
zigzagReadyConfiguration,
initialConfiguration,
mirrorTypedConfiguration,
leftZigzagSimulationTypedMachine,
mirrorTypedMachine,
zigzagSimulationTypedMachine]
congr
funext i
simpa [blankVirtualTape] using
move_left_ofBits_eq_right_archive (input i)
theorem moveLeftPrefix_leftZigzag_reaches_empty_start
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(input : Fin 2 → List Bool) :
ReachesWithin
(moveLeftPrefixTypedMachine
(leftZigzagSimulationTypedMachine baseMachine)).step
((moveLeftPrefixTypedMachine
(leftZigzagSimulationTypedMachine baseMachine)
).initialConfiguration input)
(MoveLeftPrefixState.embedConfiguration
(leftZigzagReadyConfiguration
(initialConfiguration baseMachine (fun _ : Fin 2 => []))
(fun i : Fin 2 => rawArchiveSymbols (input i))
(fun _ : Fin 2 => 0) 0))
1 := by
apply moveLeftPrefixTypedMachine_reaches
rw [moveLeftInitialConfiguration_leftZigzag_empty_archive]
exact ReachesWithin.refl _ _ _
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; bookkeeping lemma for the mission Turing-machine simulator stack.