Bounded unary-offset scheduler with explicit polynomial simulation bound
ProvedSipserGacsLautemann.bounded_unary_offset_scheduler_reports_base_accepts_with_explicit_boundcomplexity-theoryleansipser-gacs-lautemannturing-machines
Let a concrete four-tape machine and explicit polynomial upper bound be given. This theorem isolates the finite-state scheduler needed for bounded unary existential search when the simulator is allowed to run each virtual base-machine call to that explicit bound rather than to an opaque clock.
On input , the scheduler tries the virtual inputs for and reports whether the base machine accepts one of them within , where is the total three-tape input length. This is the computable scheduler obligation used by the parent reduction after extracting polynomial coefficients from the original clock and using halting-state monotonicity.
Preamble
import Definitions.Def_sgl_bounded_unary_offset_data import Definitions.Def_sgl_machine_infrastructure
Formal statement
namespace SipserGacsLautemann
theorem bounded_unary_offset_scheduler_reports_base_accepts_with_explicit_bound
(states : Nat)
(machine : Machine 4 states)
(coefficient degree : Nat) :
∃ (State : Type) (_ : Fintype State)
(scheduler : TypedMachine 3 State)
(schedulerTime : Nat → Nat),
PolynomiallyBounded schedulerTime ∧
∀ input : Fin 3 → List Bool,
scheduler.result
(scheduler.run input
(schedulerTime (totalInputLength input))).state =
some
(@decide
(∃ offset : Fin ((input 2).length + 1),
machine.acceptsWithin
(boundedUnaryOffsetInput input offset.val)
(coefficient *
(2 * totalInputLength input + 1) ^ degree))
(Classical.propDecidable _)) := by
sorry
end SipserGacsLautemann
Source
Prove2me Sipser--Gacs--Lautemann mission bounded-unary search construction; explicit-bound correction of the machine-level scheduler obligation.