sgl_machine_infrastructure
Definitioncomplexity-theoryformalizationturing-machine
A typed-state presentation of the mission’s deterministic multitape Turing machines, together with a finite-state relabeling into Fin states and exact preservation theorems for steps, runs, acceptance, rejection, and stable halting.
Definition code
import Definitions.Def_sipser_gacs_lautemann
import Mathlib.Data.Fintype.EquivFin
namespace SipserGacsLautemann
/-- A version of the mission machine whose finite state type has not yet
been relabeled as an initial segment of the natural numbers. -/
structure TypedMachine (tapes : Nat) (State : Type) where
start : State
transition :
State → (Fin tapes → TapeSymbol) →
State × (Fin tapes → TapeSymbol × HeadMove)
result : State → Option Bool
structure TypedConfiguration (tapes : Nat) (State : Type) where
state : State
tape : Fin tapes → Tape
def TypedMachine.step {tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(configuration : TypedConfiguration tapes State) :
TypedConfiguration tapes State :=
match machine.result configuration.state with
| some _ => configuration
| none =>
let action :=
machine.transition configuration.state
(fun i => (configuration.tape i).head)
{ state := action.1
tape := fun i =>
Tape.move
(Tape.write (configuration.tape i) (action.2 i).1)
(action.2 i).2 }
def TypedMachine.initialConfiguration {tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool) :
TypedConfiguration tapes State :=
⟨machine.start, fun i => Tape.ofBits (input i)⟩
def TypedMachine.run {tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool) :
Nat → TypedConfiguration tapes State
| 0 => machine.initialConfiguration input
| steps + 1 => machine.step (machine.run input steps)
noncomputable def TypedMachine.toMachine {tapes : Nat} {State : Type}
[Fintype State] (machine : TypedMachine tapes State) :
Machine tapes (Fintype.card State) :=
let encode := Fintype.equivFin State
{ start := encode machine.start
transition := fun state symbols =>
let action := machine.transition (encode.symm state) symbols
⟨encode action.1, action.2⟩
result := fun state => machine.result (encode.symm state) }
noncomputable def TypedConfiguration.encode {tapes : Nat}
{State : Type} [Fintype State]
(configuration : TypedConfiguration tapes State) :
Configuration tapes (Fintype.card State) :=
⟨Fintype.equivFin State configuration.state, configuration.tape⟩
theorem TypedMachine.toMachine_result_encode {tapes : Nat}
{State : Type} [Fintype State]
(machine : TypedMachine tapes State)
(configuration : TypedConfiguration tapes State) :
machine.toMachine.result configuration.encode.state =
machine.result configuration.state := by
simp [TypedMachine.toMachine, TypedConfiguration.encode]
theorem TypedMachine.toMachine_step_encode {tapes : Nat}
{State : Type} [Fintype State]
(machine : TypedMachine tapes State)
(configuration : TypedConfiguration tapes State) :
machine.toMachine.step configuration.encode =
(machine.step configuration).encode := by
cases hresult : machine.result configuration.state with
| some result =>
unfold Machine.step TypedMachine.step
rw [machine.toMachine_result_encode configuration, hresult]
| none =>
unfold Machine.step TypedMachine.step
rw [machine.toMachine_result_encode configuration, hresult]
simp [TypedMachine.toMachine, TypedConfiguration.encode]
theorem TypedMachine.toMachine_initial_encode {tapes : Nat}
{State : Type} [Fintype State]
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool) :
SipserGacsLautemann.initialConfiguration machine.toMachine input =
(machine.initialConfiguration input).encode := by
simp [SipserGacsLautemann.initialConfiguration,
TypedMachine.initialConfiguration,
TypedMachine.toMachine, TypedConfiguration.encode]
theorem TypedMachine.toMachine_run_encode {tapes : Nat}
{State : Type} [Fintype State]
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool) (steps : Nat) :
machine.toMachine.run input steps =
(machine.run input steps).encode := by
induction steps with
| zero =>
exact machine.toMachine_initial_encode input
| succ steps ih =>
rw [Machine.run, TypedMachine.run, ih]
exact machine.toMachine_step_encode (machine.run input steps)
theorem TypedMachine.toMachine_acceptsWithin_iff {tapes : Nat}
{State : Type} [Fintype State]
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool) (steps : Nat) :
machine.toMachine.acceptsWithin input steps ↔
machine.result (machine.run input steps).state = some true := by
unfold Machine.acceptsWithin
rw [machine.toMachine_run_encode]
exact
⟨fun h => by
simpa [TypedConfiguration.encode, TypedMachine.toMachine] using h,
fun h => by
simpa [TypedConfiguration.encode, TypedMachine.toMachine] using h⟩
theorem TypedMachine.toMachine_rejectsWithin_iff {tapes : Nat}
{State : Type} [Fintype State]
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool) (steps : Nat) :
machine.toMachine.rejectsWithin input steps ↔
machine.result (machine.run input steps).state = some false := by
unfold Machine.rejectsWithin
rw [machine.toMachine_run_encode]
exact
⟨fun h => by
simpa [TypedConfiguration.encode, TypedMachine.toMachine] using h,
fun h => by
simpa [TypedConfiguration.encode, TypedMachine.toMachine] using h⟩
theorem TypedMachine.step_eq_self_of_result_some {tapes : Nat}
{State : Type} (machine : TypedMachine tapes State)
(configuration : TypedConfiguration tapes State)
{result : Bool}
(hresult : machine.result configuration.state = some result) :
machine.step configuration = configuration := by
simp [TypedMachine.step, hresult]
theorem TypedMachine.run_add_eq_of_result_run_eq_some {tapes : Nat}
{State : Type} (machine : TypedMachine tapes State)
(input : Fin tapes → List Bool)
(steps extra : Nat) {result : Bool}
(hresult :
machine.result (machine.run input steps).state = some result) :
machine.run input (steps + extra) = machine.run input steps := by
induction extra with
| zero => simp
| succ extra ih =>
rw [Nat.add_succ, TypedMachine.run, ih]
exact
machine.step_eq_self_of_result_some
(machine.run input steps) hresult
end SipserGacsLautemannSource
Reusable formal infrastructure for the custom Turing-machine model in the Sipser–Gács–Lautemann mission.