SGL machine halting monotonicity
Definitionsgl_machine_monotonecomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module proves basic monotonicity facts for the mission Turing-machine model. Once a machine has reached an accepting or rejecting state, subsequent steps leave it in the same halted configuration, so acceptance and rejection persist under larger time bounds.
These lemmas are runtime-padding infrastructure for polynomial-time simulations in the Sipser--Gacs--Lautemann mission.
Definition code
import Definitions.Def_sipser_gacs_lautemann
namespace SipserGacsLautemann
theorem Machine.step_eq_self_of_result_eq_some
{tapes states : Nat}
(machine : Machine tapes states)
(configuration : Configuration tapes states)
{result : Bool}
(hresult : machine.result configuration.state = some result) :
machine.step configuration = configuration := by
simp [Machine.step, hresult]
theorem Machine.run_add_of_result_eq_some
{tapes states : Nat}
(machine : Machine tapes states)
(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, Machine.run, ih]
exact
machine.step_eq_self_of_result_eq_some
(machine.run input steps) hresult
theorem Machine.acceptsWithin_mono_steps
{tapes states : Nat}
(machine : Machine tapes states)
(input : Fin tapes → List Bool)
{earlier later : Nat}
(hle : earlier ≤ later)
(haccepts : machine.acceptsWithin input earlier) :
machine.acceptsWithin input later := by
obtain ⟨extra, rfl⟩ := Nat.exists_eq_add_of_le hle
unfold Machine.acceptsWithin at haccepts ⊢
rw [machine.run_add_of_result_eq_some
input earlier extra haccepts]
exact haccepts
theorem Machine.rejectsWithin_mono_steps
{tapes states : Nat}
(machine : Machine tapes states)
(input : Fin tapes → List Bool)
{earlier later : Nat}
(hle : earlier ≤ later)
(hrejects : machine.rejectsWithin input earlier) :
machine.rejectsWithin input later := by
obtain ⟨extra, rfl⟩ := Nat.exists_eq_add_of_le hle
unfold Machine.rejectsWithin at hrejects ⊢
rw [machine.run_add_of_result_eq_some
input earlier extra hrejects]
exact hrejects
theorem Machine.not_accepts_and_rejects_same_time
{tapes states : Nat}
(machine : Machine tapes states)
(input : Fin tapes → List Bool)
(steps : Nat) :
¬ (machine.acceptsWithin input steps ∧
machine.rejectsWithin input steps) := by
intro hboth
rcases hboth with ⟨haccepts, hrejects⟩
unfold Machine.acceptsWithin at haccepts
unfold Machine.rejectsWithin at hrejects
rw [haccepts] at hrejects
cases hrejects
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.