A Turing machine decides the fused evaluation scan in product time
ProvedCookLevin.evalScan_machineThere is a Turing machine with a constant number of tapes and work symbols that decides the fused single-pass evaluation scan in time c times (|x|+1) times (|w|+1), where x is the input CNF string and w the certificate bits. The machine mirrors the automaton scanAux: the control modes become machine states, the unary counter and the clause and formula accumulators live on work tapes, and the certificate w is consulted by a read head that walks to the indexed bit and back. A single left-to-right pass over the input string suffices; the per-literal lookup walks telescope, so the total number of steps is bounded by the product bound.
Preamble
import Definitions.Def_CookLevin_evalScan
Formal statement
namespace CookLevin
theorem evalScan_machine :
∃ (M : Machine) (k G c : Nat),
TuringMachine k G M ∧
∀ x w : List Bool,
DecidesIn M k (boolsToSymbols x) (boolsToSymbols w)
(c * (x.length + 1) * (w.length + 1))
(evalScan x w) := by sorry
end CookLevinSource
Definitions/Def_CookLevin_evalScan; machine half of the decomposition of CookLevin.decodeCnf_evaluate_machine