Cover single-shift raw rewriter reaches transformed initial tapes
DisprovedSipserGacsLautemann.cover_single_shift_query_rewriter_reaches_transformed_initialcomplexity-theoryleansipser-gacs-lautemannturing-machines
This is the raw finite-state rewriting subgoal for the single-shift cover preprocessor. It asserts that there is a finite typed four-tape rewriter and a polynomial clock which, on input , first reaches a distinguished ready state exactly at the declared finish time with the tapes reset to the transformed initial input . Here is the decoded translation block selected by .
The theorem also records the two control facts needed by the generic wrapper: before the declared finish time the run has not yet reached ready, and the rewriter is nonhalting. These make it possible to wrap the rewriter with an arbitrary verifier machine and prove exact step-by-step delegation after preprocessing.
Preamble
import Definitions.Def_sgl_cover_preprocess_transform import Definitions.Def_sgl_machine_infrastructure
Formal statement
namespace SipserGacsLautemann
theorem cover_single_shift_query_rewriter_reaches_transformed_initial :
∃ (RewriteState : Type) (_ : Fintype RewriteState)
(rewriter : TypedMachine 4 RewriteState)
(ready : RewriteState)
(rewriteTime : Nat → Nat),
PolynomiallyBounded rewriteTime ∧
(∀ input : Fin 4 → List Bool,
rewriter.run input
(rewriteTime (totalInputLength input)) =
{ state := ready
tape := fun i =>
Tape.ofBits
(coverSingleShiftPreprocessInput input i) }) ∧
(∀ (input : Fin 4 → List Bool) (steps : Nat),
steps < rewriteTime (totalInputLength input) →
(rewriter.run input steps).state ≠ ready) ∧
(∀ (input : Fin 4 → List Bool) (steps : Nat),
steps < rewriteTime (totalInputLength input) →
rewriter.result (rewriter.run input steps).state = none) := by
sorry
end SipserGacsLautemann
Source
Prove2me Sipser--Gacs--Lautemann mission finite-state preprocessor construction; isolates the raw decoded-shift XOR rewriter needed by the machine-level cover verifier.