Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Cover single-shift raw rewriter reaches transformed initial tapes

Disproved
SipserGacsLautemann.cover_single_shift_query_rewriter_reaches_transformed_initial

by Henry Yuen · Jul 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-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 (x,e,u,o)(x,e,u,o)(x,e,u,o), first reaches a distinguished ready state exactly at the declared finish time with the tapes reset to the transformed initial input (x,e,u⊕ti,o)(x,e,u \oplus t_i,o)(x,e,u⊕ti​,o). Here tit_iti​ is the decoded translation block selected by i=min⁡(∣o∣,∣u∣)i=\min(|o|,|u|)i=min(∣o∣,∣u∣).

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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me