Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A Turing machine that finds the first accepted prefix of a zero-padded input and then computes on it

Proved
OPIBridge.cookLevin_prefixSearch

by sragavan · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

simulationturing-machinesuniformity

Searching for the first accepted prefix, inside one Turing machine. Let MVM_VMV​ and MMM be legal multi-tape Turing machines (published Cook–Levin model) computing functions vvv and ggg on bit strings, in time cV(n+1)dVc_V(n+1)^{d_V}cV​(n+1)dV​ and c(n+1)dc(n+1)^dc(n+1)d respectively.

For a bit string zzz and s≥0s\ge0s≥0, write z[s]z_{[s]}z[s]​ for the first sss bits of z 0∞z\,0^\inftyz0∞.

Then there are a legal machine NNN (with kNk_NkN​ tapes and alphabet size GNG_NGN​) and constants a,ba,ba,b with the following property. Let zzz and s0s_0s0​ satisfy

v(z[s])=[false]  (s<s0),v(z[s0])=[true].v(z_{[s]})=[\mathrm{false}]\ \ (s<s_0),\qquad v(z_{[s_0]})=[\mathrm{true}].v(z[s]​)=[false]  (s<s0​),v(z[s0​]​)=[true].

Start NNN with input tape ▹ z 0∞\triangleright\,z\,0^\infty▹z0∞ (zero padding instead of blanks, so there is no end marker) and all other tapes empty. Then NNN halts within T≤a(s0+1)bT\le a(s_0+1)^bT≤a(s0​+1)b steps, and its output (the bits from cell 111 of its last tape) is g(z[s0])g(z_{[s_0]})g(z[s0​]​).

NNN tries s=0,1,2,…s=0,1,2,\dotss=0,1,2,… in turn: it runs MVM_VMV​ on z[s]z_{[s]}z[s]​; on rejection it clears MVM_VMV​'s work tapes and appends the next input bit; on acceptance it runs MMM on z[s]z_{[s]}z[s]​. Together with OPIBridge.bitProgram_ofCookLevin, this gives OPIBridge.bitProgram_prefixSearch.

Formalization Note. Machines are CookLevin.Machines; legality is CookLevin.TuringMachine; running time and output are CookLevin.ComputesInTime, execute and outputOf. In the start configuration, the input tape holds startSymbol in cell 000 and boolSym of the zero-padded bits after it.

Preamble
import Mathlib
import Definitions.Def_CookLevin_Cost
Formal statement
namespace OPIBridge

open CookLevin

theorem cookLevin_prefixSearch (MV : Machine) (kV GV cV dV : ℕ) (v : List Bool → List Bool)
    (hMV : TuringMachine kV GV MV) (hv : ComputesInTime MV kV (polyBound cV dV) v)
    (M : Machine) (k G c d : ℕ) (g : List Bool → List Bool)
    (hM : TuringMachine k G M) (hg : ComputesInTime M k (polyBound c d) g) :
    ∃ (N : Machine) (kN GN a b : ℕ), TuringMachine kN GN N ∧
      ∀ (z : List Bool) (s₀ : ℕ),
        (∀ s < s₀, v ((z ++ List.replicate s false).take s) = [false]) →
        v ((z ++ List.replicate s₀ false).take s₀) = [true] →
        ∃ T ≤ a * (s₀ + 1) ^ b,
          (execute N (0, ((fun i => if i = 0 then startSymbol else boolSym (z.getD (i - 1) false)), 0) ::
            List.replicate (kN - 1) (contents [], 0)) T).1 = N.length ∧
          outputOf kN (execute N (0, ((fun i => if i = 0 then startSymbol else
            boolSym (z.getD (i - 1) false)), 0) :: List.replicate (kN - 1) (contents [], 0)) T) (T + 2) =
            g ((z ++ List.replicate s₀ false).take s₀) := by sorry

end OPIBridge
Source
Standard composition of multi-tape Turing machines (Arora–Barak, Computational Complexity: A Modern Approach, 2009, §1.2–1.3), in the CookLevin machine model of the platform; used for the uniformity requirement of Ragavan–Shutty, arXiv:2610.00502, Theorem 7.4.

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