Cook–Levin machines run inside OPI bit programs, with a search for the input's end
ProvedOPIBridge.bitProgram_prefixSearchLet and be two legal multi-tape Turing machines (the published Cook–Levin model: finite alphabet, read-only input tape, output on the last tape). Suppose computes a function and computes a function on bit strings, each in time on inputs of length .
For a bit string and , let denote the first bits of , that is, padded with zeros and cut to length .
Then there are one public bit program (an OPI BitOracleProgram using no coins and no oracle queries) and constants with the following property. Let be any bit string and a number such that
Run on input , where the cells after read as and there is no end marker. Then halts successfully with output exactly , within steps, with charged time and number of visited cells also at most .
In words, the bit program searches for the first prefix length accepted by and then outputs 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).
import Mathlib import Definitions.Def_QAlgorithms_Defs_OPIBitPrograms import Definitions.Def_CookLevin_Cost
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