SGL encoded simulator
Definitionsgl_encoded_simulatorcomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module formalizes a fixed two-bit encoding of mission tape symbols and proves that an encoded simulator can reproduce a base multitape machine run with constant-factor overhead. It supplies the low-level encoded-tape correctness lemmas used by the Sipser--Gacs--Lautemann simulator stack.
Definition code
import Definitions.Def_sgl_machine_infrastructure
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.Fintype.Sum
import Mathlib.Tactic.FinCases
namespace SipserGacsLautemann
def encodeTapeSymbol : TapeSymbol → Bool × Bool
| .blank => (false, false)
| .bit false => (false, true)
| .bit true => (true, false)
def decodeTapeSymbol : Bool × Bool → TapeSymbol
| (false, false) => .blank
| (false, true) => .bit false
| (true, false) => .bit true
| (true, true) => .blank
@[simp]
theorem decodeTapeSymbol_encodeTapeSymbol (symbol : TapeSymbol) :
decodeTapeSymbol (encodeTapeSymbol symbol) = symbol := by
cases symbol with
| blank => rfl
| bit value =>
cases value <;> rfl
def encodedSymbolBits (symbol : TapeSymbol) : List Bool :=
[(encodeTapeSymbol symbol).1, (encodeTapeSymbol symbol).2]
def encodedLeftSymbols (symbols : List TapeSymbol) :
List TapeSymbol :=
symbols.flatMap fun symbol =>
[.bit (encodeTapeSymbol symbol).2,
.bit (encodeTapeSymbol symbol).1]
def encodedRightSymbols (head : TapeSymbol)
(symbols : List TapeSymbol) : List TapeSymbol :=
.bit (encodeTapeSymbol head).2 ::
symbols.flatMap fun symbol =>
[.bit (encodeTapeSymbol symbol).1,
.bit (encodeTapeSymbol symbol).2]
def encodeTape (tape : Tape) : Tape where
left := encodedLeftSymbols tape.left
head := .bit (encodeTapeSymbol tape.head).1
right := encodedRightSymbols tape.head tape.right
def encodeInputBits (bits : List Bool) : List Bool :=
match bits with
| [] => encodedSymbolBits .blank
| _ => bits.flatMap fun bit => encodedSymbolBits (.bit bit)
theorem encodedSymbols_map_bits (bits : List Bool) :
(bits.map TapeSymbol.bit).flatMap
(fun symbol =>
[.bit (encodeTapeSymbol symbol).1,
.bit (encodeTapeSymbol symbol).2]) =
(bits.flatMap fun bit =>
encodedSymbolBits (.bit bit)).map TapeSymbol.bit := by
induction bits with
| nil => rfl
| cons bit bits ih =>
simp [encodedSymbolBits, ih]
theorem encodeTape_ofBits (bits : List Bool) :
encodeTape (Tape.ofBits bits) =
Tape.ofBits (encodeInputBits bits) := by
cases bits with
| nil =>
simp [encodeTape, Tape.ofBits, encodeInputBits,
encodedLeftSymbols, encodedRightSymbols,
encodedSymbolBits, encodeTapeSymbol]
| cons bit bits =>
simp [encodeTape, Tape.ofBits, encodeInputBits,
encodedLeftSymbols, encodedRightSymbols,
encodedSymbolBits, List.flatMap_cons,
encodedSymbols_map_bits]
inductive EncodedSimulationState
(tapes baseStates : Nat) where
| ready : Fin baseStates →
EncodedSimulationState tapes baseStates
| readSecond :
Fin baseStates → (Fin tapes → Bool) →
EncodedSimulationState tapes baseStates
| writeFirst :
Fin baseStates →
(Fin tapes → Bool × Bool) →
(Fin tapes → HeadMove) →
EncodedSimulationState tapes baseStates
| moveSecond :
Fin baseStates → (Fin tapes → HeadMove) →
EncodedSimulationState tapes baseStates
| ensureFirst :
Fin baseStates →
EncodedSimulationState tapes baseStates
| ensureSecond :
Fin baseStates →
EncodedSimulationState tapes baseStates
def EncodedSimulationState.equivSum
(tapes baseStates : Nat) :
EncodedSimulationState tapes baseStates ≃
Fin baseStates ⊕
(Fin baseStates × (Fin tapes → Bool)) ⊕
(Fin baseStates ×
(Fin tapes → Bool × Bool) ×
(Fin tapes → HeadMove)) ⊕
(Fin baseStates × (Fin tapes → HeadMove)) ⊕
Fin baseStates ⊕ Fin baseStates where
toFun
| .ready state => Sum.inl state
| .readSecond state first =>
Sum.inr (Sum.inl (state, first))
| .writeFirst state writes moves =>
Sum.inr (Sum.inr
(Sum.inl (state, writes, moves)))
| .moveSecond state moves =>
Sum.inr (Sum.inr
(Sum.inr (Sum.inl (state, moves))))
| .ensureFirst state =>
Sum.inr (Sum.inr
(Sum.inr (Sum.inr (Sum.inl state))))
| .ensureSecond state =>
Sum.inr (Sum.inr
(Sum.inr (Sum.inr (Sum.inr state))))
invFun
| Sum.inl state => .ready state
| Sum.inr (Sum.inl (state, first)) =>
.readSecond state first
| Sum.inr (Sum.inr
(Sum.inl (state, writes, moves))) =>
.writeFirst state writes moves
| Sum.inr (Sum.inr
(Sum.inr (Sum.inl (state, moves)))) =>
.moveSecond state moves
| Sum.inr (Sum.inr
(Sum.inr (Sum.inr (Sum.inl state)))) =>
.ensureFirst state
| Sum.inr (Sum.inr
(Sum.inr (Sum.inr (Sum.inr state)))) =>
.ensureSecond state
left_inv state := by
cases state <;> rfl
right_inv state := by
rcases state with
state | state | state | state | state | state <;>
rfl
def headMoveEquivFin : HeadMove ≃ Fin 3 where
toFun
| .left => 0
| .stay => 1
| .right => 2
invFun
| ⟨0, _⟩ => .left
| ⟨1, _⟩ => .stay
| ⟨2, _⟩ => .right
left_inv move := by
cases move <;> rfl
right_inv i := by
fin_cases i <;> rfl
instance headMoveFintype : Fintype HeadMove where
elems := {.left, .stay, .right}
complete move := by cases move <;> simp
def tapeSymbolEquivFin : TapeSymbol ≃ Fin 3 where
toFun
| .blank => 0
| .bit false => 1
| .bit true => 2
invFun
| ⟨0, _⟩ => .blank
| ⟨1, _⟩ => .bit false
| ⟨2, _⟩ => .bit true
left_inv symbol := by
cases symbol with
| blank => rfl
| bit value => cases value <;> rfl
right_inv i := by
fin_cases i <;> rfl
instance tapeSymbolFintype : Fintype TapeSymbol where
elems := {.blank, .bit false, .bit true}
complete symbol := by
cases symbol with
| blank => simp
| bit value => cases value <;> simp
noncomputable instance encodedSimulationStateFintype
(tapes baseStates : Nat) :
Fintype (EncodedSimulationState tapes baseStates) :=
Fintype.ofEquiv
(Fin baseStates ⊕
(Fin baseStates × (Fin tapes → Bool)) ⊕
(Fin baseStates ×
(Fin tapes → Bool × Bool) ×
(Fin tapes → HeadMove)) ⊕
(Fin baseStates × (Fin tapes → HeadMove)) ⊕
Fin baseStates ⊕ Fin baseStates)
(EncodedSimulationState.equivSum tapes baseStates).symm
def readPhysicalBit : TapeSymbol → Bool
| .blank => false
| .bit bit => bit
def preserveOrEncodeBlank (symbol : TapeSymbol) :
TapeSymbol :=
.bit (readPhysicalBit symbol)
def firstPhysicalMove : HeadMove → HeadMove
| .left => .left
| .stay => .stay
| .right => .right
def secondPhysicalMove : HeadMove → HeadMove
| .left => .left
| .stay => .stay
| .right => .right
noncomputable def encodedSimulationTypedMachine
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates) :
TypedMachine tapes
(EncodedSimulationState tapes baseStates) where
start := .ready baseMachine.start
transition state symbols :=
match state with
| .ready baseState =>
(.readSecond baseState
(fun i => readPhysicalBit (symbols i)),
fun i =>
(preserveOrEncodeBlank (symbols i), .right))
| .readSecond baseState firstBits =>
let virtualSymbols := fun i =>
decodeTapeSymbol
(firstBits i, readPhysicalBit (symbols i))
let action :=
baseMachine.transition baseState virtualSymbols
(.writeFirst action.1
(fun i => encodeTapeSymbol (action.2 i).1)
(fun i => (action.2 i).2),
fun i =>
(.bit (encodeTapeSymbol (action.2 i).1).2,
.left))
| .writeFirst nextState writes moves =>
(.moveSecond nextState moves,
fun i =>
(.bit (writes i).1,
firstPhysicalMove (moves i)))
| .moveSecond nextState moves =>
(.ensureFirst nextState,
fun i => (symbols i, secondPhysicalMove (moves i)))
| .ensureFirst nextState =>
(.ensureSecond nextState,
fun i =>
(preserveOrEncodeBlank (symbols i), .right))
| .ensureSecond nextState =>
(.ready nextState,
fun i =>
(preserveOrEncodeBlank (symbols i), .left))
result
| .ready baseState => baseMachine.result baseState
| _ => none
def encodeTypedConfiguration {tapes baseStates : Nat}
(configuration : Configuration tapes baseStates) :
TypedConfiguration tapes
(EncodedSimulationState tapes baseStates) :=
⟨.ready configuration.state,
fun i => encodeTape (configuration.tape i)⟩
theorem encodedSimulation_initial
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(input : Fin tapes → List Bool) :
(encodedSimulationTypedMachine baseMachine).initialConfiguration
(fun i => encodeInputBits (input i)) =
encodeTypedConfiguration
(initialConfiguration baseMachine input) := by
unfold TypedMachine.initialConfiguration
encodeTypedConfiguration initialConfiguration
congr
funext i
exact (encodeTape_ofBits (input i)).symm
theorem encodeTape_write (tape : Tape)
(symbol : TapeSymbol) :
encodeTape (tape.write symbol) =
{ encodeTape tape with
head := .bit (encodeTapeSymbol symbol).1
right :=
.bit (encodeTapeSymbol symbol).2 ::
(encodeTape tape).right.tail } := by
cases tape
rfl
theorem encodeTape_move_stay (tape : Tape) :
encodeTape (tape.move .stay) = encodeTape tape := by
rfl
def applyTapeAction (tape : Tape)
(symbol : TapeSymbol) (move : HeadMove) : Tape :=
Tape.move (Tape.write tape symbol) move
def encodedTapeVirtualStep (tape : Tape)
(write : TapeSymbol) (move : HeadMove) : Tape :=
let afterReadFirst :=
applyTapeAction tape
(preserveOrEncodeBlank tape.head) .right
let afterWriteSecond :=
applyTapeAction afterReadFirst
(.bit (encodeTapeSymbol write).2) .left
let afterWriteFirst :=
applyTapeAction afterWriteSecond
(.bit (encodeTapeSymbol write).1)
(firstPhysicalMove move)
let afterMoveSecond :=
applyTapeAction afterWriteFirst afterWriteFirst.head
(secondPhysicalMove move)
let afterEnsureFirst :=
applyTapeAction afterMoveSecond
(preserveOrEncodeBlank afterMoveSecond.head) .right
applyTapeAction afterEnsureFirst
(preserveOrEncodeBlank afterEnsureFirst.head) .left
theorem encodedTapeVirtualStep_encodeTape
(tape : Tape) (write : TapeSymbol)
(move : HeadMove) :
encodedTapeVirtualStep (encodeTape tape) write move =
encodeTape
(Tape.move (Tape.write tape write) move) := by
cases tape with
| mk left head right =>
cases move with
| stay =>
cases write <;>
simp [encodedTapeVirtualStep, applyTapeAction,
encodeTape, Tape.move, Tape.write,
encodedLeftSymbols, encodedRightSymbols,
preserveOrEncodeBlank, readPhysicalBit,
firstPhysicalMove, secondPhysicalMove,
encodeTapeSymbol]
| right =>
cases right with
| nil =>
cases write <;>
simp [encodedTapeVirtualStep, applyTapeAction,
encodeTape, Tape.move, Tape.write,
encodedLeftSymbols, encodedRightSymbols,
preserveOrEncodeBlank, readPhysicalBit,
firstPhysicalMove, secondPhysicalMove,
encodeTapeSymbol]
| cons next rest =>
cases write <;> cases next <;>
simp [encodedTapeVirtualStep, applyTapeAction,
encodeTape, Tape.move, Tape.write,
encodedLeftSymbols, encodedRightSymbols,
preserveOrEncodeBlank, readPhysicalBit,
firstPhysicalMove, secondPhysicalMove,
encodeTapeSymbol]
| left =>
cases left with
| nil =>
cases write <;>
simp [encodedTapeVirtualStep, applyTapeAction,
encodeTape, Tape.move, Tape.write,
encodedLeftSymbols, encodedRightSymbols,
preserveOrEncodeBlank, readPhysicalBit,
firstPhysicalMove, secondPhysicalMove,
encodeTapeSymbol]
| cons previous rest =>
cases write <;> cases previous <;>
simp [encodedTapeVirtualStep, applyTapeAction,
encodeTape, Tape.move, Tape.write,
encodedLeftSymbols, encodedRightSymbols,
preserveOrEncodeBlank, readPhysicalBit,
firstPhysicalMove, secondPhysicalMove,
encodeTapeSymbol]
theorem decodeEncodedTapeHead (tape : Tape) :
decodeTapeSymbol
(readPhysicalBit (encodeTape tape).head,
readPhysicalBit
(applyTapeAction (encodeTape tape)
(preserveOrEncodeBlank (encodeTape tape).head)
.right).head) =
tape.head := by
cases tape with
| mk left head right =>
cases head with
| blank => rfl
| bit value =>
cases value <;> rfl
noncomputable def encodedSimulationSixSteps
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(configuration :
TypedConfiguration tapes
(EncodedSimulationState tapes baseStates)) :
TypedConfiguration tapes
(EncodedSimulationState tapes baseStates) :=
let machine := encodedSimulationTypedMachine baseMachine
machine.step
(machine.step
(machine.step
(machine.step
(machine.step
(machine.step configuration)))))
theorem encodedSimulationSixSteps_encode
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(configuration : Configuration tapes baseStates) :
encodedSimulationSixSteps baseMachine
(encodeTypedConfiguration configuration) =
encodeTypedConfiguration
(baseMachine.step configuration) := by
cases configuration with
| mk state tape =>
cases hresult : baseMachine.result state with
| some result =>
simp [encodedSimulationSixSteps,
TypedMachine.step,
encodedSimulationTypedMachine,
encodeTypedConfiguration,
Machine.step, hresult]
| none =>
have hread :
(fun i =>
decodeTapeSymbol
(readPhysicalBit (encodeTape (tape i)).head,
readPhysicalBit
(applyTapeAction
(encodeTape (tape i))
(preserveOrEncodeBlank
(encodeTape (tape i)).head)
.right).head)) =
fun i => (tape i).head := by
funext i
exact decodeEncodedTapeHead (tape i)
simp only [applyTapeAction] at hread
simp only [encodedSimulationSixSteps,
encodeTypedConfiguration,
TypedMachine.step,
encodedSimulationTypedMachine,
hresult, Machine.step]
rw [hread]
let action :=
baseMachine.transition state
(fun i => (tape i).head)
change
({ state := .ready action.1
tape := fun i =>
encodedTapeVirtualStep
(encodeTape (tape i))
(action.2 i).1 (action.2 i).2 } :
TypedConfiguration tapes
(EncodedSimulationState tapes baseStates)) =
({ state := .ready action.1
tape := fun i =>
encodeTape
(Tape.move
(Tape.write (tape i) (action.2 i).1)
(action.2 i).2) } :
TypedConfiguration tapes
(EncodedSimulationState tapes baseStates))
congr
funext i
exact
encodedTapeVirtualStep_encodeTape
(tape i) (action.2 i).1 (action.2 i).2
theorem encodedSimulation_run_add_six
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(input : Fin tapes → List Bool) (steps : Nat) :
(encodedSimulationTypedMachine baseMachine).run
input (steps + 6) =
encodedSimulationSixSteps baseMachine
((encodedSimulationTypedMachine baseMachine).run
input steps) := by
simp [encodedSimulationSixSteps, TypedMachine.run,
Nat.add_assoc]
theorem encodedSimulation_run_encoded
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(input : Fin tapes → List Bool) (steps : Nat) :
(encodedSimulationTypedMachine baseMachine).run
(fun i => encodeInputBits (input i)) (6 * steps) =
encodeTypedConfiguration
(baseMachine.run input steps) := by
induction steps with
| zero =>
simpa [TypedMachine.run] using
encodedSimulation_initial baseMachine input
| succ steps ih =>
have htime : 6 * (steps + 1) = 6 * steps + 6 := by
omega
rw [htime,
encodedSimulation_run_add_six baseMachine,
ih,
encodedSimulationSixSteps_encode]
rfl
theorem encodedSimulation_result_run_encoded
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(input : Fin tapes → List Bool) (steps : Nat) :
(encodedSimulationTypedMachine baseMachine).result
((encodedSimulationTypedMachine baseMachine).run
(fun i => encodeInputBits (input i))
(6 * steps)).state =
baseMachine.result
(baseMachine.run input steps).state := by
rw [encodedSimulation_run_encoded]
rfl
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.