Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Cook–Levin machines run inside OPI bit programs, with a search for the input's end

Proved
OPIBridge.bitProgram_prefixSearch

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

quantum-algorithmssimulationturing-machinesuniformity

Let MVM_VMV​ and MMM be two legal multi-tape Turing machines (the published Cook–Levin model: finite alphabet, read-only input tape, output on the last tape). Suppose MVM_VMV​ computes a function vvv and MMM computes a function ggg on bit strings, each in time c (n+1)dc\,(n+1)^dc(n+1)d on inputs of length nnn.

For a bit string zzz and s≥0s\ge 0s≥0, let z[s]z_{[s]}z[s]​ denote the first sss bits of z 0∞z\,0^\inftyz0∞, that is, zzz padded with zeros and cut to length sss.

Then there are one public bit program BBB (an OPI BitOracleProgram using no coins and no oracle queries) and constants a,ba,ba,b with the following property. Let zzz be any bit string and s0s_0s0​ a number such that

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

Run BBB on input zzz, where the cells after zzz read as 000 and there is no end marker. Then BBB halts successfully with output exactly g(z[s0])g(z_{[s_0]})g(z[s0​]​), within a (s0+∣z∣+1)ba\,(s_0+|z|+1)^ba(s0​+∣z∣+1)b steps, with charged time and number of visited cells also at most a (s0+∣z∣+1)ba\,(s_0+|z|+1)^ba(s0​+∣z∣+1)b.

In words, the bit program searches for the first prefix length accepted by vvv and then outputs ggg of that prefix. This turns word-RAM or Turing-machine algorithms into constructors of UniformResourceFamilys, whose bit machine sees its input without an end marker.

Formalization Note. Machines are CookLevin.Machines with CookLevin.TuringMachine k G M (legality) and CookLevin.ComputesInTime (exact output on the last tape after the time bound). The bit program is executed by bitProgramExecution with no oracle and no coins (both constant false).

Preamble
import Mathlib
import Definitions.Def_QAlgorithms_Defs_OPIBitPrograms
import Definitions.Def_CookLevin_Cost
Formal statement
namespace OPIBridge

open QAlgorithms.OPI

theorem bitProgram_prefixSearch
    (MV : CookLevin.Machine) (kV GV cV dV : ℕ) (v : List Bool → List Bool)
    (hMV : CookLevin.TuringMachine kV GV MV)
    (hv : CookLevin.ComputesInTime MV kV (CookLevin.polyBound cV dV) v)
    (M : CookLevin.Machine) (k G c d : ℕ) (g : List Bool → List Bool)
    (hM : CookLevin.TuringMachine k G M)
    (hg : CookLevin.ComputesInTime M k (CookLevin.polyBound c d) g) :
    ∃ B : BitOracleProgram, IsPublicPreprocessor B ∧ ∃ a b : ℕ,
      ∀ (z : List Bool) (s₀ : ℕ),
        (∀ s < s₀, v ((z ++ List.replicate s false).take s) = [false]) →
        v ((z ++ List.replicate s₀ false).take s₀) = [true] →
        ∃ fuel ≤ a * (s₀ + z.length + 1) ^ b,
          let result := bitProgramExecution B z (fun _ => false) (fun _ => false) fuel
          result.status = some true ∧
            result.output = g ((z ++ List.replicate s₀ false).take s₀) ∧
            result.time ≤ a * (s₀ + z.length + 1) ^ b ∧
            result.visited.card ≤ a * (s₀ + z.length + 1) ^ b := by sorry

end OPIBridge
Source
Standard simulation of multi-tape Turing machines (Arora–Barak, Computational Complexity, §1.2–1.3, Claims 1.5–1.6), specialised to the OPI bit-program model (QAlgorithms.OPI.BitOracleProgram) of the platform; used for the uniformity requirement of Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held), §7.3, Theorem 7.4, p.40 ("running in poly(m, q, log(1/ϵ)) time") and §5.2 "Computational conventions", p.26.

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