Preprocess-and-delegate DPT theorem up to observational equivalence, full module
Definitionsgl_preprocess_delegate_obseq_fullcomplexity-theorysipser-gacs-lautemannturing-machines
Full-code module proving a robust preprocess-and-delegate theorem for deterministic polynomial-time machines. The preprocessing phase may reach a base configuration only observationally equivalent to the transformed initial configuration; exact equality of Lean’s concrete tape zipper is unnecessary. This supports machine-construction reductions where scans may leave harmless blank padding.
Definition code
import Definitions.Def_sgl_preprocess_delegate
import Definitions.Def_sgl_tape_observational_equivalence_full
namespace SipserGacsLautemann
/-- Variant of `DecidesInPolynomialTime.of_same_tape_preprocess_delegate`
where the preprocessing phase only has to reach a base configuration
observationally equivalent to the transformed initial configuration.
This is the useful form for concrete Turing-machine transducers: scanning to
the end of a finite input and returning to the origin may leave extra blank
cells in the concrete zipper representation, but those cells are invisible to
all future machine executions. -/
theorem DecidesInPolynomialTime.of_same_tape_preprocess_delegate_obsEq
{tapes states : Nat} {State : Type}
[Fintype State]
{predicate : (Fin tapes → List Bool) → Prop}
(baseMachine : Machine tapes states)
(baseTime : Nat → Nat)
(hbaseTime : PolynomiallyBounded baseTime)
(hbaseCorrect :
∀ input : Fin tapes → List Bool,
(baseMachine.acceptsWithin input
(baseTime (totalInputLength input)) ↔
predicate input) ∧
(baseMachine.rejectsWithin input
(baseTime (totalInputLength input)) ↔
¬ predicate input))
(transform :
(Fin tapes → List Bool) → (Fin tapes → List Bool))
(preMachine : TypedMachine tapes State)
(preTime argumentBound : Nat → Nat)
(hpreTime : PolynomiallyBounded preTime)
(hargumentBound : PolynomiallyBounded argumentBound)
(htransformLength :
∀ input : Fin tapes → List Bool,
totalInputLength (transform input) ≤
argumentBound (totalInputLength input))
(embed : Configuration tapes states →
TypedConfiguration tapes State)
(preConfig :
(Fin tapes → List Bool) → Configuration tapes states)
(hpreConfigObsEq :
∀ input : Fin tapes → List Bool,
Configuration.ObsEq (preConfig input)
(initialConfiguration baseMachine
(transform input)))
(hpre :
∀ input : Fin tapes → List Bool,
preMachine.run input
(preTime (totalInputLength input)) =
embed (preConfig input))
(hstep :
∀ configuration : Configuration tapes states,
preMachine.step (embed configuration) =
embed (baseMachine.step configuration))
(hresult :
∀ configuration : Configuration tapes states,
preMachine.result (embed configuration).state =
baseMachine.result configuration.state) :
DecidesInPolynomialTime
(fun input : Fin tapes → List Bool =>
predicate (transform input)) := by
rcases hbaseTime with
⟨coefficient, degree, hbaseBound⟩
let paddedBaseTime : Nat → Nat :=
fun n => coefficient * (argumentBound n + 1) ^ degree
let totalTime : Nat → Nat :=
fun n => preTime n + paddedBaseTime n
let machine := preMachine.toMachine
refine
⟨Fintype.card State, machine, totalTime,
hpreTime.add
(PolynomiallyBounded.padded_composed_bound
hargumentBound coefficient degree),
?_⟩
intro input
let baseInput := transform input
let inputLength := totalInputLength input
let exactBaseSteps := baseTime (totalInputLength baseInput)
let paddedBaseSteps := paddedBaseTime inputLength
have hbaseStepsLe :
exactBaseSteps ≤ paddedBaseSteps := by
dsimp [exactBaseSteps, paddedBaseSteps, paddedBaseTime]
have hlength :
totalInputLength baseInput + 1 ≤
argumentBound inputLength + 1 :=
Nat.succ_le_succ (htransformLength input)
exact
(hbaseBound (totalInputLength baseInput)).trans
(Nat.mul_le_mul_left coefficient
(Nat.pow_le_pow_left hlength degree))
have hbaseCorrectLater :
(baseMachine.acceptsWithin baseInput paddedBaseSteps ↔
predicate baseInput) ∧
(baseMachine.rejectsWithin baseInput paddedBaseSteps ↔
¬ predicate baseInput) := by
exact
baseMachine.correctness_at_larger_time
predicate baseInput hbaseStepsLe
(hbaseCorrect baseInput).1
(hbaseCorrect baseInput).2
have hrun :
preMachine.run input
(preTime inputLength + paddedBaseSteps) =
embed
((baseMachine.step^[paddedBaseSteps])
(preConfig input)) := by
rw [preMachine.run_add_steps]
rw [hpre]
exact
preprocessDelegate_iterate_embed
preMachine baseMachine embed hstep
(preConfig input) paddedBaseSteps
have hbaseResultObs :
baseMachine.result
(((baseMachine.step^[paddedBaseSteps])
(preConfig input)).state) =
baseMachine.result
(baseMachine.run baseInput paddedBaseSteps).state := by
rw [Machine.run_eq_iterate_step_from_initial]
exact
baseMachine.result_iterate_eq_of_obsEq
(hpreConfigObsEq input) paddedBaseSteps
constructor
· rw [preMachine.toMachine_acceptsWithin_iff]
change
preMachine.result
(preMachine.run input
(totalTime (totalInputLength input))).state =
some true ↔
predicate (transform input)
simp only [totalTime, paddedBaseTime]
rw [hrun]
rw [hresult]
rw [hbaseResultObs]
simpa [Machine.acceptsWithin, baseInput,
paddedBaseSteps] using hbaseCorrectLater.1
· rw [preMachine.toMachine_rejectsWithin_iff]
change
preMachine.result
(preMachine.run input
(totalTime (totalInputLength input))).state =
some false ↔
¬ predicate (transform input)
simp only [totalTime, paddedBaseTime]
rw [hrun]
rw [hresult]
rw [hbaseResultObs]
simpa [Machine.rejectsWithin, baseInput,
paddedBaseSteps] using hbaseCorrectLater.2
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; full-code replacement using sgl_tape_observational_equivalence_full.