Exact cover single-shift preprocessing delegate machine
OpenSipserGacsLautemann.cover_single_shift_query_preprocessor_delegates_to_selected_verifier_machineLet a concrete four-tape verifier machine be given. This theorem isolates the exact finite-state preprocessing wrapper needed for one decoded cover-shift query. It asserts that there is a finite typed preprocessing machine which, on input , reaches the exact initial configuration of the verifier machine on the transformed input , where is decoded from at , and then delegates every subsequent step and halting result to the verifier machine.
The preprocessing clock is polynomially bounded. Together with the same-tape delegation helper, this is precisely the remaining low-level machine-construction obligation for the single-shift cover verifier.
Preamble
import Definitions.Def_sgl_cover_preprocess_transform import Definitions.Def_sgl_preprocess_delegate
Formal statement
namespace SipserGacsLautemann
theorem cover_single_shift_query_preprocessor_delegates_to_selected_verifier_machine
(states : Nat)
(machine : Machine 4 states) :
∃ (State : Type) (_ : Fintype State)
(preMachine : TypedMachine 4 State)
(preTime : Nat → Nat)
(embed : Configuration 4 states →
TypedConfiguration 4 State),
PolynomiallyBounded preTime ∧
(∀ input : Fin 4 → List Bool,
preMachine.run input
(preTime (totalInputLength input)) =
embed (initialConfiguration machine
(coverSingleShiftPreprocessInput input))) ∧
(∀ configuration : Configuration 4 states,
preMachine.step (embed configuration) =
embed (machine.step configuration)) ∧
(∀ configuration : Configuration 4 states,
preMachine.result (embed configuration).state =
machine.result configuration.state) := by
sorry
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission: machine-level cover single-shift preprocessing obligation.