Single-shift cover query scheduler with explicit polynomial simulation bound
ProvedSipserGacsLautemann.cover_single_shift_query_reports_base_accepts_with_explicit_boundcomplexity-theoryleansipser-gacs-lautemannturing-machines
Let a concrete four-tape verifier machine and an explicit polynomial upper bound be given. This theorem isolates the result-only machine-construction obligation for one decoded cover-shift query.
On input , the scheduler computes the transformed virtual input , where is the decoded block selected by , runs or simulates the supplied base machine on that virtual input up to the explicit bound , and reports whether the base machine accepts. Unlike the earlier one-step delegation formulation, this statement only requires the final Boolean result, so it is compatible with representation-based simulator implementations that do not reset raw tapes to exact Tape.ofBits form.
Preamble
import Definitions.Def_sgl_cover_preprocess_transform import Definitions.Def_sgl_machine_infrastructure
Formal statement
namespace SipserGacsLautemann
theorem cover_single_shift_query_reports_base_accepts_with_explicit_bound
(states : Nat)
(machine : Machine 4 states)
(coefficient degree : Nat) :
∃ (State : Type) (_ : Fintype State)
(scheduler : TypedMachine 4 State)
(schedulerTime : Nat → Nat),
PolynomiallyBounded schedulerTime ∧
∀ input : Fin 4 → List Bool,
scheduler.result
(scheduler.run input
(schedulerTime (totalInputLength input))).state =
some
(@decide
(machine.acceptsWithin
(coverSingleShiftPreprocessInput input)
(coefficient *
(totalInputLength input + 1) ^ degree))
(Classical.propDecidable _)) := by
sorry
end SipserGacsLautemann
Source
Prove2me Sipser--Gacs--Lautemann mission cover-query machine construction; result-only explicit-bound correction of the single-shift preprocessing obligation.