SGL raw input as right archive
Definitionsgl_raw_archive_layoutcomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module relates the mission machine initial tape layout to the mirrored zigzag simulator layout. It defines a raw archive encoding and proves that moving left from Tape.ofBits bits gives a blank-head tape whose right side is exactly the raw input archive and whose encoded work side is blank.
This is a small but necessary bridge for schedulers that preserve raw inputs while building encoded verifier-query work tapes.
Definition code
import Definitions.Def_sgl_left_zigzag_global_packaged
namespace SipserGacsLautemann
def rawArchiveSymbols : List Bool → List TapeSymbol
| [] => [.blank]
| bits => bits.map .bit
def blankVirtualTape : Tape :=
⟨[], .blank, []⟩
theorem move_left_ofBits_eq_right_archive
(bits : List Bool) :
(Tape.ofBits bits).move .left =
mirrorTape
(zigzagPhysicalTape (rawArchiveSymbols bits)
blankVirtualTape 0 0) := by
cases bits with
| nil =>
rfl
| cons bit bits =>
rfl
theorem left_archive_initial_tape
(bits : List Bool) :
(Tape.ofBits bits).move .left =
(leftZigzagReadyConfiguration
(initialConfiguration
({ start := 0
transition := fun state symbols =>
(state, fun i => (symbols i, .stay))
result := fun _ => none } : Machine 2 1)
(fun _ : Fin 2 => []))
(fun _ : Fin 2 => rawArchiveSymbols bits)
(fun _ : Fin 2 => 0) 0).tape 0 := by
rw [move_left_ofBits_eq_right_archive]
rfl
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.