SGL move-left prefix composition
Definitionsgl_move_left_prefixcomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module defines a generic typed-machine prefix that first moves every tape left once, then runs an arbitrary typed machine from the resulting configuration. It proves that after the prefix step, the composed machine has exactly the same state and tape behavior as the underlying typed machine started from the moved-left initial tapes.
This is scheduler infrastructure for preserving raw input archives before invoking encoded verifier simulations.
Definition code
import Definitions.Def_sgl_raw_archive_machine
import Mathlib.Data.Fintype.Sum
namespace SipserGacsLautemann
inductive MoveLeftPrefixState (State : Type) where
| moveLeft
| running : State → MoveLeftPrefixState State
deriving DecidableEq, Fintype
def moveLeftInitialConfiguration
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool) :
TypedConfiguration tapes State where
state := machine.start
tape := fun i => (Tape.ofBits (input i)).move .left
def MoveLeftPrefixState.embedConfiguration
{tapes : Nat} {State : Type}
(configuration : TypedConfiguration tapes State) :
TypedConfiguration tapes (MoveLeftPrefixState State) where
state := .running configuration.state
tape := configuration.tape
def moveLeftPrefixTypedMachine
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State) :
TypedMachine tapes (MoveLeftPrefixState State) where
start := .moveLeft
transition state symbols :=
match state with
| .moveLeft =>
(.running machine.start,
fun i => (symbols i, .left))
| .running baseState =>
let action := machine.transition baseState symbols
(.running action.1, action.2)
result
| .moveLeft => none
| .running baseState => machine.result baseState
theorem moveLeftPrefixTypedMachine_step_running
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(configuration : TypedConfiguration tapes State) :
(moveLeftPrefixTypedMachine machine).step
(MoveLeftPrefixState.embedConfiguration configuration) =
MoveLeftPrefixState.embedConfiguration
(machine.step configuration) := by
cases configuration with
| mk state tape =>
cases hresult : machine.result state with
| some result =>
simp [TypedMachine.step,
moveLeftPrefixTypedMachine,
MoveLeftPrefixState.embedConfiguration,
hresult]
| none =>
simp [TypedMachine.step,
moveLeftPrefixTypedMachine,
MoveLeftPrefixState.embedConfiguration,
hresult]
theorem moveLeftPrefixTypedMachine_run_one
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool) :
(moveLeftPrefixTypedMachine machine).run input 1 =
MoveLeftPrefixState.embedConfiguration
(moveLeftInitialConfiguration machine input) := by
rfl
theorem moveLeftPrefixTypedMachine_run_succ
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool)
(steps : Nat) :
(moveLeftPrefixTypedMachine machine).run input
(steps + 1) =
MoveLeftPrefixState.embedConfiguration
((machine.step^[steps])
(moveLeftInitialConfiguration machine input)) := by
induction steps with
| zero =>
exact moveLeftPrefixTypedMachine_run_one machine input
| succ steps ih =>
change
(moveLeftPrefixTypedMachine machine).run input
((steps + 1) + 1) =
MoveLeftPrefixState.embedConfiguration
((machine.step^[steps + 1])
(moveLeftInitialConfiguration machine input))
rw [TypedMachine.run, ih]
rw [moveLeftPrefixTypedMachine_step_running]
rw [Function.iterate_succ_apply']
theorem moveLeftPrefixTypedMachine_result_run_succ
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool)
(steps : Nat) :
(moveLeftPrefixTypedMachine machine).result
((moveLeftPrefixTypedMachine machine).run input
(steps + 1)).state =
machine.result
(((machine.step^[steps])
(moveLeftInitialConfiguration machine input)).state) := by
rw [moveLeftPrefixTypedMachine_run_succ]
rfl
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.