SGL zigzag simulator machine
Definitionsgl_zigzag_simulatorcomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module defines the finite-state zigzag simulator used to run a two-tape mission machine inside encoded work regions while preserving archive data on the physical tapes. It includes the simulator states, local scan and update procedures, mirroring operations, and the mirrored left-zigzag simulator.
Definition code
import Definitions.Def_sgl_encoded_simulator
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.Fintype.Sigma
import Mathlib.Data.Fintype.Sum
import Mathlib.Tactic.DeriveFintype
namespace SipserGacsLautemann
inductive ZigzagIndexClass where
| zero
| positiveOne
| positive
| negative
deriving DecidableEq, Fintype
def ZigzagIndexClass.next : ZigzagIndexClass →
ZigzagIndexClass
| .zero => .positiveOne
| .positiveOne => .negative
| .positive => .negative
| .negative => .positive
inductive ZigzagDirection where
| inward
| outward
deriving DecidableEq, Fintype
def ZigzagDirection.headMove : ZigzagDirection → HeadMove
| .inward => .left
| .outward => .right
structure ZigzagRelocation where
direction : ZigzagDirection
distance : Fin 7
deriving DecidableEq, Fintype
def zigzagRelocation (move : HeadMove)
(indexClass : ZigzagIndexClass) :
Option ZigzagRelocation :=
match move, indexClass with
| .stay, _ => none
| .right, .zero =>
some ⟨.outward, ⟨3, by decide⟩⟩
| .right, .positiveOne =>
some ⟨.outward, ⟨6, by decide⟩⟩
| .right, .positive =>
some ⟨.outward, ⟨6, by decide⟩⟩
| .right, .negative =>
some ⟨.inward, ⟨6, by decide⟩⟩
| .left, .zero =>
some ⟨.outward, ⟨6, by decide⟩⟩
| .left, .positiveOne =>
some ⟨.inward, ⟨3, by decide⟩⟩
| .left, .positive =>
some ⟨.inward, ⟨6, by decide⟩⟩
| .left, .negative =>
some ⟨.outward, ⟨6, by decide⟩⟩
inductive ZigzagScanLocal where
| atFlag : ZigzagIndexClass → ZigzagScanLocal
| atSymbolFirst :
ZigzagIndexClass → Bool → ZigzagScanLocal
| atSymbolSecond :
ZigzagIndexClass → Bool → Bool → ZigzagScanLocal
| returning :
TapeSymbol → ZigzagIndexClass → ZigzagScanLocal
| done :
TapeSymbol → ZigzagIndexClass → ZigzagScanLocal
deriving DecidableEq, Fintype
def ZigzagScanLocal.isDone : ZigzagScanLocal → Bool
| .done _ _ => true
| _ => false
def ZigzagScanLocal.symbol : ZigzagScanLocal → TapeSymbol
| .done symbol _ => symbol
| _ => .blank
def ZigzagScanLocal.indexClass :
ZigzagScanLocal → ZigzagIndexClass
| .atFlag indexClass => indexClass
| .atSymbolFirst indexClass _ => indexClass
| .atSymbolSecond indexClass _ _ => indexClass
| .returning _ indexClass => indexClass
| .done _ indexClass => indexClass
def zigzagScanLocalStep
(scanState : ZigzagScanLocal) (symbol : TapeSymbol) :
ZigzagScanLocal × (TapeSymbol × HeadMove) :=
match scanState with
| .atFlag indexClass =>
(.atSymbolFirst indexClass
(readPhysicalBit symbol),
(preserveOrEncodeBlank symbol, .right))
| .atSymbolFirst indexClass headFlag =>
(.atSymbolSecond indexClass headFlag
(readPhysicalBit symbol),
(preserveOrEncodeBlank symbol, .right))
| .atSymbolSecond indexClass headFlag firstBit =>
let decoded :=
decodeTapeSymbol (firstBit, readPhysicalBit symbol)
if headFlag then
(.returning decoded indexClass,
(preserveOrEncodeBlank symbol, .left))
else
(.atFlag indexClass.next,
(preserveOrEncodeBlank symbol, .right))
| .returning cached indexClass =>
match symbol with
| .blank =>
(.done cached indexClass, (.blank, .stay))
| .bit bit =>
(.returning cached indexClass, (.bit bit, .left))
| .done cached indexClass =>
(.done cached indexClass, (symbol, .stay))
inductive ZigzagUpdateLocal where
| atFlag : ZigzagIndexClass → ZigzagUpdateLocal
| skipSymbolFirst : ZigzagIndexClass → ZigzagUpdateLocal
| skipSymbolSecond : ZigzagIndexClass → ZigzagUpdateLocal
| writeSymbolFirst :
ZigzagIndexClass → ZigzagUpdateLocal
| writeSymbolSecond :
ZigzagIndexClass → ZigzagUpdateLocal
| returnToFlag :
ZigzagIndexClass → ZigzagUpdateLocal
| relocate :
ZigzagDirection → Fin 7 → ZigzagUpdateLocal
| setHead
| ensureSymbolFirst
| ensureSymbolSecond
| returning
| done
deriving DecidableEq, Fintype
def ZigzagUpdateLocal.isDone : ZigzagUpdateLocal → Bool
| .done => true
| _ => false
def finPredSeven (remaining : Fin 7)
(hpositive : 0 < remaining.val) : Fin 7 :=
⟨remaining.val - 1, by omega⟩
def zigzagUpdateLocalStep
(write : TapeSymbol) (move : HeadMove)
(updateState : ZigzagUpdateLocal) (symbol : TapeSymbol) :
ZigzagUpdateLocal × (TapeSymbol × HeadMove) :=
match updateState with
| .atFlag indexClass =>
if readPhysicalBit symbol then
(.writeSymbolFirst indexClass,
(.bit false, .right))
else
(.skipSymbolFirst indexClass,
(preserveOrEncodeBlank symbol, .right))
| .skipSymbolFirst indexClass =>
(.skipSymbolSecond indexClass,
(preserveOrEncodeBlank symbol, .right))
| .skipSymbolSecond indexClass =>
(.atFlag indexClass.next,
(preserveOrEncodeBlank symbol, .right))
| .writeSymbolFirst indexClass =>
(.writeSymbolSecond indexClass,
(.bit (encodeTapeSymbol write).1, .right))
| .writeSymbolSecond indexClass =>
(.returnToFlag indexClass,
(.bit (encodeTapeSymbol write).2, .left))
| .returnToFlag indexClass =>
match zigzagRelocation move indexClass with
| none =>
(.setHead, (preserveOrEncodeBlank symbol, .left))
| some relocation =>
(.relocate relocation.direction relocation.distance,
(preserveOrEncodeBlank symbol, .left))
| .relocate direction remaining =>
if hzero : remaining.val = 0 then
(.setHead, (preserveOrEncodeBlank symbol, .stay))
else
(.relocate direction
(finPredSeven remaining
(Nat.pos_of_ne_zero hzero)),
(preserveOrEncodeBlank symbol,
direction.headMove))
| .setHead =>
(.ensureSymbolFirst, (.bit true, .right))
| .ensureSymbolFirst =>
(.ensureSymbolSecond,
(preserveOrEncodeBlank symbol, .right))
| .ensureSymbolSecond =>
(.returning,
(preserveOrEncodeBlank symbol, .left))
| .returning =>
match symbol with
| .blank => (.done, (.blank, .stay))
| .bit bit => (.returning, (.bit bit, .left))
| .done => (.done, (symbol, .stay))
def allScanDone (locals : Fin 2 → ZigzagScanLocal) : Bool :=
(locals 0).isDone && (locals 1).isDone
def allUpdateDone
(locals : Fin 2 → ZigzagUpdateLocal) : Bool :=
(locals 0).isDone && (locals 1).isDone
inductive ZigzagSimulationState (baseStates : Nat) where
| ready : Fin baseStates →
ZigzagSimulationState baseStates
| scanning :
Fin baseStates → (Fin 2 → ZigzagScanLocal) →
ZigzagSimulationState baseStates
| updating :
Fin baseStates →
(Fin 2 → TapeSymbol) →
(Fin 2 → HeadMove) →
(Fin 2 → ZigzagUpdateLocal) →
ZigzagSimulationState baseStates
def ZigzagSimulationState.equivSum (baseStates : Nat) :
ZigzagSimulationState baseStates ≃
Fin baseStates ⊕
(Fin baseStates × (Fin 2 → ZigzagScanLocal)) ⊕
(Fin baseStates ×
(Fin 2 → TapeSymbol) ×
(Fin 2 → HeadMove) ×
(Fin 2 → ZigzagUpdateLocal)) where
toFun
| .ready state => Sum.inl state
| .scanning state locals =>
Sum.inr (Sum.inl (state, locals))
| .updating state writes moves locals =>
Sum.inr (Sum.inr
(state, writes, moves, locals))
invFun
| Sum.inl state => .ready state
| Sum.inr (Sum.inl (state, locals)) =>
.scanning state locals
| Sum.inr (Sum.inr
(state, writes, moves, locals)) =>
.updating state writes moves locals
left_inv state := by
cases state <;> rfl
right_inv state := by
rcases state with state | state | state <;> rfl
noncomputable instance zigzagSimulationStateFintype
(baseStates : Nat) :
Fintype (ZigzagSimulationState baseStates) :=
Fintype.ofEquiv
(Fin baseStates ⊕
(Fin baseStates × (Fin 2 → ZigzagScanLocal)) ⊕
(Fin baseStates ×
(Fin 2 → TapeSymbol) ×
(Fin 2 → HeadMove) ×
(Fin 2 → ZigzagUpdateLocal)))
(ZigzagSimulationState.equivSum baseStates).symm
def startScanLocals : Fin 2 → ZigzagScanLocal :=
fun _ => .atFlag .zero
def startUpdateLocals : Fin 2 → ZigzagUpdateLocal :=
fun _ => .atFlag .zero
noncomputable def zigzagSimulationTypedMachine
{baseStates : Nat}
(baseMachine : Machine 2 baseStates) :
TypedMachine 2 (ZigzagSimulationState baseStates) where
start := .ready baseMachine.start
transition state symbols :=
match state with
| .ready baseState =>
(.scanning baseState startScanLocals,
fun i => (symbols i, .right))
| .scanning baseState locals =>
if hdone : allScanDone locals = true then
let virtualSymbols :=
fun i => (locals i).symbol
let action :=
baseMachine.transition baseState virtualSymbols
(.updating action.1
(fun i => (action.2 i).1)
(fun i => (action.2 i).2)
startUpdateLocals,
fun i => (symbols i, .right))
else
let actions :=
fun i => zigzagScanLocalStep (locals i) (symbols i)
(.scanning baseState (fun i => (actions i).1),
fun i => (actions i).2)
| .updating nextState writes moves locals =>
if hdone : allUpdateDone locals = true then
(.ready nextState, fun i => (symbols i, .stay))
else
let actions :=
fun i =>
zigzagUpdateLocalStep
(writes i) (moves i) (locals i) (symbols i)
(.updating nextState writes moves
(fun i => (actions i).1),
fun i => (actions i).2)
result
| .ready baseState => baseMachine.result baseState
| _ => none
def mirrorHeadMove : HeadMove → HeadMove
| .left => .right
| .stay => .stay
| .right => .left
@[simp]
theorem mirrorHeadMove_involutive (move : HeadMove) :
mirrorHeadMove (mirrorHeadMove move) = move := by
cases move <;> rfl
def mirrorTape (tape : Tape) : Tape where
left := tape.right
head := tape.head
right := tape.left
@[simp]
theorem mirrorTape_involutive (tape : Tape) :
mirrorTape (mirrorTape tape) = tape := by
cases tape
rfl
@[simp]
theorem mirrorTape_write (tape : Tape)
(symbol : TapeSymbol) :
mirrorTape (tape.write symbol) =
(mirrorTape tape).write symbol := by
cases tape
rfl
@[simp]
theorem mirrorTape_move (tape : Tape) (move : HeadMove) :
mirrorTape (tape.move move) =
(mirrorTape tape).move (mirrorHeadMove move) := by
cases tape with
| mk left head right =>
cases move <;> cases left <;> cases right <;> rfl
def mirrorTapeAction :
TapeSymbol × HeadMove → TapeSymbol × HeadMove :=
fun action => (action.1, mirrorHeadMove action.2)
def mirrorTypedMachine {tapes : Nat} {State : Type}
(machine : TypedMachine tapes State) :
TypedMachine tapes State where
start := machine.start
transition state symbols :=
let action := machine.transition state symbols
(action.1, fun i => mirrorTapeAction (action.2 i))
result := machine.result
def mirrorTypedConfiguration {tapes : Nat} {State : Type}
(configuration : TypedConfiguration tapes State) :
TypedConfiguration tapes State :=
⟨configuration.state, fun i => mirrorTape (configuration.tape i)⟩
@[simp]
theorem mirrorTypedConfiguration_involutive
{tapes : Nat} {State : Type}
(configuration : TypedConfiguration tapes State) :
mirrorTypedConfiguration
(mirrorTypedConfiguration configuration) =
configuration := by
cases configuration
simp [mirrorTypedConfiguration]
theorem mirrorTypedMachine_step
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(configuration : TypedConfiguration tapes State) :
(mirrorTypedMachine machine).step
(mirrorTypedConfiguration configuration) =
mirrorTypedConfiguration (machine.step configuration) := by
cases configuration with
| mk state tape =>
cases hresult : machine.result state with
| some result =>
simp [TypedMachine.step, mirrorTypedMachine,
mirrorTypedConfiguration, hresult]
| none =>
simp only [TypedMachine.step, mirrorTypedMachine,
mirrorTypedConfiguration, hresult]
let action :=
machine.transition state (fun i => (tape i).head)
change
({ state := action.1
tape := fun i =>
Tape.move
(Tape.write (mirrorTape (tape i))
(action.2 i).1)
(mirrorHeadMove (action.2 i).2) } :
TypedConfiguration tapes State) =
({ state := action.1
tape := fun i =>
mirrorTape
(Tape.move
(Tape.write (tape i) (action.2 i).1)
(action.2 i).2) } :
TypedConfiguration tapes State)
congr 1
funext i
simp
noncomputable def leftZigzagSimulationTypedMachine
{baseStates : Nat}
(baseMachine : Machine 2 baseStates) :
TypedMachine 2 (ZigzagSimulationState baseStates) :=
mirrorTypedMachine
(zigzagSimulationTypedMachine baseMachine)
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.