Cook–Levin machines on zero-padded input are simulated by OPI bit programs in linear time
ProvedOPIBridge.bitProgram_ofCookLevinLinear-time simulation of a Cook–Levin machine by an OPI bit program. Let be a legal multi-tape Turing machine in the published Cook–Levin model, with tapes and alphabet size . Its input tape is read-only, and its output is the bit string written from cell of its last tape.
For a bit string , start with the input tape holding in cell and then the bits of followed by infinitely many zeros, so that there is no blank and no end marker. All other tapes are empty.
Then there are one public OPI bit program (no coins, no oracle queries) and a constant such that, for every and every : if is halted after steps, then run on input halts successfully within steps. Its output equals the output of , its charged time is at most , and it visits at most cells.
This connects classical machine models to the bit programs of UniformResourceFamily, whose input has no end marker: the zero padding matches the bit machine's convention that cells beyond the input read as .
Formalization Note. The machine's output is CookLevin.outputOf k (execute N cfg T) (T + 2), i.e. the bits from cell of tape up to the first non-bit cell. The bit program uses bit tapes per work tape (binary digits of the symbol) plus an origin marker, and one decision tree per state of .
import Mathlib import Definitions.Def_QAlgorithms_Defs_OPIBitPrograms import Definitions.Def_CookLevin_Cost
namespace OPIBridge
open QAlgorithms.OPI CookLevin
theorem bitProgram_ofCookLevin (N : Machine) (k G : ℕ) (hN : TuringMachine k G N) :
∃ B : BitOracleProgram, IsPublicPreprocessor B ∧ ∃ C : ℕ,
∀ (z : List Bool) (T : ℕ),
(execute N (0, ((fun i => if i = 0 then startSymbol else boolSym (z.getD (i - 1) false)), 0) ::
List.replicate (k - 1) (contents [], 0)) T).1 = N.length →
∃ fuel ≤ C * (T + 1),
(bitProgramExecution B z (fun _ => false) (fun _ => false) fuel).status = some true ∧
(bitProgramExecution B z (fun _ => false) (fun _ => false) fuel).output =
outputOf k (execute N (0, ((fun i => if i = 0 then startSymbol else
boolSym (z.getD (i - 1) false)), 0) :: List.replicate (k - 1) (contents [], 0)) T) (T + 2) ∧
(bitProgramExecution B z (fun _ => false) (fun _ => false) fuel).time ≤ C * (T + 1) ∧
(bitProgramExecution B z (fun _ => false) (fun _ => false) fuel).visited.card ≤
z.length + C * (T + 1) := by sorry
end OPIBridge