SGL tape reindexing closure
Definitionsgl_tape_reindexcomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module formalizes that the mission Turing-machine model is invariant under a finite renaming of tape indices. If a predicate is decidable in polynomial time on tapes, then the predicate obtained by composing its input with any equivalence of finite tape index sets is decidable in the same polynomial time.
The module defines the reindexed machine, proves that runs, accepting states, rejecting states, and total input length are preserved by the tape equivalence, and packages these facts as a reusable DecidesInPolynomialTime.reindexTapes closure lemma for the Sipser--Gacs--Lautemann mission.
Definition code
import Definitions.Def_sipser_gacs_lautemann
import Mathlib.Algebra.BigOperators.Fin
namespace SipserGacsLautemann
def Configuration.reindexTapes {oldTapes newTapes states : Nat}
(equiv : Fin newTapes ≃ Fin oldTapes)
(configuration : Configuration newTapes states) :
Configuration oldTapes states where
state := configuration.state
tape := fun i => configuration.tape (equiv.symm i)
def Machine.reindexTapes {oldTapes newTapes states : Nat}
(machine : Machine oldTapes states)
(equiv : Fin newTapes ≃ Fin oldTapes) :
Machine newTapes states where
start := machine.start
transition := fun state symbols =>
let action :=
machine.transition state
(fun i => symbols (equiv.symm i))
⟨action.1, fun j => action.2 (equiv j)⟩
result := machine.result
theorem Machine.reindexTapes_step {oldTapes newTapes states : Nat}
(machine : Machine oldTapes states)
(equiv : Fin newTapes ≃ Fin oldTapes)
(configuration : Configuration newTapes states) :
((machine.reindexTapes equiv).step configuration
).reindexTapes equiv =
machine.step (configuration.reindexTapes equiv) := by
cases configuration with
| mk state tape =>
cases hresult : machine.result state with
| some result =>
simp [Machine.step, Machine.reindexTapes,
Configuration.reindexTapes, hresult]
| none =>
simp only [Machine.step, Machine.reindexTapes,
Configuration.reindexTapes, hresult]
congr 1
funext i
simp
theorem Machine.reindexTapes_initial {oldTapes newTapes states : Nat}
(machine : Machine oldTapes states)
(equiv : Fin newTapes ≃ Fin oldTapes)
(input : Fin newTapes → List Bool) :
(initialConfiguration (machine.reindexTapes equiv) input
).reindexTapes equiv =
initialConfiguration machine (fun i => input (equiv.symm i)) := by
rfl
theorem Machine.reindexTapes_run {oldTapes newTapes states : Nat}
(machine : Machine oldTapes states)
(equiv : Fin newTapes ≃ Fin oldTapes)
(input : Fin newTapes → List Bool) (steps : Nat) :
((machine.reindexTapes equiv).run input steps
).reindexTapes equiv =
machine.run (fun i => input (equiv.symm i)) steps := by
induction steps with
| zero => exact machine.reindexTapes_initial equiv input
| succ steps ih =>
simp only [Machine.run]
rw [machine.reindexTapes_step equiv]
exact congrArg machine.step ih
theorem Machine.reindexTapes_acceptsWithin {oldTapes newTapes states : Nat}
(machine : Machine oldTapes states)
(equiv : Fin newTapes ≃ Fin oldTapes)
(input : Fin newTapes → List Bool) (steps : Nat) :
(machine.reindexTapes equiv).acceptsWithin input steps ↔
machine.acceptsWithin
(fun i => input (equiv.symm i)) steps := by
unfold Machine.acceptsWithin
rw [← machine.reindexTapes_run equiv input steps]
rfl
theorem Machine.reindexTapes_rejectsWithin {oldTapes newTapes states : Nat}
(machine : Machine oldTapes states)
(equiv : Fin newTapes ≃ Fin oldTapes)
(input : Fin newTapes → List Bool) (steps : Nat) :
(machine.reindexTapes equiv).rejectsWithin input steps ↔
machine.rejectsWithin
(fun i => input (equiv.symm i)) steps := by
unfold Machine.rejectsWithin
rw [← machine.reindexTapes_run equiv input steps]
rfl
theorem totalInputLength_reindex {oldTapes newTapes : Nat}
(equiv : Fin newTapes ≃ Fin oldTapes)
(input : Fin newTapes → List Bool) :
totalInputLength (fun i : Fin oldTapes => input (equiv.symm i)) =
totalInputLength input := by
simp only [totalInputLength, List.sum_ofFn]
exact
(Fintype.sum_equiv equiv
(fun i : Fin newTapes => (input i).length)
(fun j : Fin oldTapes => (input (equiv.symm j)).length)
(by intro i; simp)).symm
theorem DecidesInPolynomialTime.reindexTapes {oldTapes newTapes : Nat}
{predicate : (Fin oldTapes → List Bool) → Prop}
(hpredicate : DecidesInPolynomialTime predicate)
(equiv : Fin newTapes ≃ Fin oldTapes) :
DecidesInPolynomialTime
(fun input : Fin newTapes → List Bool =>
predicate (fun i => input (equiv.symm i))) := by
rcases hpredicate with
⟨states, machine, time, htime, hcorrect⟩
refine
⟨states, machine.reindexTapes equiv, time, htime, ?_⟩
intro input
have hlength := totalInputLength_reindex equiv input
have hbase := hcorrect (fun i => input (equiv.symm i))
constructor
· rw [machine.reindexTapes_acceptsWithin]
simpa [hlength] using hbase.1
· rw [machine.reindexTapes_rejectsWithin]
simpa [hlength] using hbase.2
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.