A Turing machine that finds the first accepted prefix of a zero-padded input and then computes on it
ProvedOPIBridge.cookLevin_prefixSearchSearching for the first accepted prefix, inside one Turing machine. Let and be legal multi-tape Turing machines (published Cook–Levin model) computing functions and on bit strings, in time and respectively.
For a bit string and , write for the first bits of .
Then there are a legal machine (with tapes and alphabet size ) and constants with the following property. Let and satisfy
Start with input tape (zero padding instead of blanks, so there is no end marker) and all other tapes empty. Then halts within steps, and its output (the bits from cell of its last tape) is .
tries in turn: it runs on ; on rejection it clears 's work tapes and appends the next input bit; on acceptance it runs on . 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 and boolSym of the zero-padded bits after it.
import Mathlib import Definitions.Def_CookLevin_Cost
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