SGL move-left raw archive phase
Definitionsgl_raw_archive_machinecomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module defines a finite typed machine that moves every tape left once from the standard mission initial configuration. It proves that after this one-step phase each physical tape is in the right-archive layout from sgl_raw_archive_layout: the raw input is preserved on the right side of a blank head, while the encoded work side is blank.
This is the first scheduler phase needed before using the mirrored zigzag simulator on raw Prove2me inputs.
Definition code
import Definitions.Def_sgl_raw_archive_layout
namespace SipserGacsLautemann
inductive MoveLeftOnceState where
| start
| done
deriving DecidableEq, Fintype
def moveLeftOnceTypedMachine (tapes : Nat) :
TypedMachine tapes MoveLeftOnceState where
start := .start
transition state symbols :=
match state with
| .start => (.done, fun i => (symbols i, .left))
| .done => (.done, fun i => (symbols i, .stay))
result
| .start => none
| .done => none
theorem moveLeftOnceTypedMachine_step_initial
{tapes : Nat}
(input : Fin tapes → List Bool) :
(moveLeftOnceTypedMachine tapes).run input 1 =
{ state := .done
tape := fun i => (Tape.ofBits (input i)).move .left } := by
funext
rfl
theorem moveLeftOnceTypedMachine_tape_rawArchive
{tapes : Nat}
(input : Fin tapes → List Bool)
(i : Fin tapes) :
((moveLeftOnceTypedMachine tapes).run input 1).tape i =
mirrorTape
(zigzagPhysicalTape
(rawArchiveSymbols (input i))
blankVirtualTape 0 0) := by
rw [moveLeftOnceTypedMachine_step_initial]
exact move_left_ofBits_eq_right_archive (input i)
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.