Single-shift cover preprocessing rewriter reaches observationally equivalent tapes
ProvedSipserGacsLautemann.cover_single_shift_query_rewriter_reaches_transformed_initial_obseqcomplexity-theorysipser-gacs-lautemannturing-machine
There is a finite-state four-tape rewriter for the single-shift cover preprocessing map.
For every four-tape Boolean input , after a polynomially bounded number of steps , the rewriter is in a designated ready state. At that time, each output tape is observationally equivalent to the corresponding tape obtained by applying the preprocessing transform .
The theorem also states that the ready state is first reached at the scheduled time and that the rewriter reports no Boolean result before then. This isolates the tape-rewriting component needed before delegating to an arbitrary selected verifier machine.
Preamble
import Definitions.Def_sgl_cover_preprocess_transform import Definitions.Def_sgl_tape_observational_equivalence_full
Formal statement
namespace SipserGacsLautemann
theorem cover_single_shift_query_rewriter_reaches_transformed_initial_obseq :
∃ (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) ∧
(∀ input : Fin 4 → List Bool,
∀ i : Fin 4,
Tape.ObsEq
((rewriter.run input
(rewriteTime (totalInputLength input))).tape 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 SipserGacsLautemannSource
Internal decomposition lemma for the Prove2me mission “The Sipser–Gács–Lautemann Theorem”; refines the existing single-shift preprocessing rewriter obligation to observational tape equivalence.