Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact cover single-shift preprocessing delegate machine

Open
SipserGacsLautemann.cover_single_shift_query_preprocessor_delegates_to_selected_verifier_machine

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

Let 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 (x,e,u,o)(x,e,u,o)(x,e,u,o), reaches the exact initial configuration of the verifier machine on the transformed input (x,e,u⊕ti,o)(x,e,u \oplus t_i,o)(x,e,u⊕ti​,o), where tit_iti​ is decoded from eee at i=min⁡(∣o∣,∣u∣)i=\min(|o|,|u|)i=min(∣o∣,∣u∣), 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.

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