Machine correctness is preserved under larger time bounds
Definitionsgl_machine_time_paddingcomplexity-theorypolynomial-timeturing-machines
This module proves a standard padding lemma for the mission Turing-machine model. If a deterministic machine decides a predicate correctly at an exact time bound , then it also decides the same predicate correctly at any larger time bound .
The proof uses the published monotonicity lemmas for accepting and rejecting halting states, together with the fact that a deterministic machine cannot accept and reject at the same time. This is needed by scheduler constructions, which usually run submachines for a uniform polynomial upper bound rather than their exact stopping time.
Definition code
import Definitions.Def_sgl_machine_monotone
namespace SipserGacsLautemann
theorem Machine.correctness_at_larger_time
{tapes states : Nat}
(machine : Machine tapes states)
(predicate : (Fin tapes → List Bool) → Prop)
(input : Fin tapes → List Bool)
{exact later : Nat}
(hle : exact ≤ later)
(hacceptExact :
machine.acceptsWithin input exact ↔ predicate input)
(hrejectExact :
machine.rejectsWithin input exact ↔ ¬ predicate input) :
(machine.acceptsWithin input later ↔ predicate input) ∧
(machine.rejectsWithin input later ↔
¬ predicate input) := by
constructor
· constructor
· intro hacceptLater
by_contra hnot
have hrejectExact := hrejectExact.mpr hnot
have hrejectLater :=
machine.rejectsWithin_mono_steps
input hle hrejectExact
exact
machine.not_accepts_and_rejects_same_time
input later ⟨hacceptLater, hrejectLater⟩
· intro hpredicate
exact
machine.acceptsWithin_mono_steps input hle
(hacceptExact.mpr hpredicate)
· constructor
· intro hrejectLater hpredicate
have hacceptExact := hacceptExact.mpr hpredicate
have hacceptLater :=
machine.acceptsWithin_mono_steps
input hle hacceptExact
exact
machine.not_accepts_and_rejects_same_time
input later ⟨hacceptLater, hrejectLater⟩
· intro hnot
exact
machine.rejectsWithin_mono_steps input hle
(hrejectExact.mpr hnot)
theorem Machine.correctness_package_at_larger_time
{tapes states : Nat}
(machine : Machine tapes states)
(predicate : (Fin tapes → List Bool) → Prop)
(exact later : (Fin tapes → List Bool) → Nat)
(hle : ∀ input, exact input ≤ later input)
(hcorrect :
∀ input : Fin tapes → List Bool,
(machine.acceptsWithin input (exact input) ↔
predicate input) ∧
(machine.rejectsWithin input (exact input) ↔
¬ predicate input)) :
∀ input : Fin tapes → List Bool,
(machine.acceptsWithin input (later input) ↔
predicate input) ∧
(machine.rejectsWithin input (later input) ↔
¬ predicate input) := by
intro input
exact
machine.correctness_at_larger_time
predicate input (hle input)
(hcorrect input).1 (hcorrect input).2
end SipserGacsLautemann
Source
Standard deterministic-machine time padding argument for the Prove2me Sipser--Gács--Lautemann scheduler formalization.