Cook–Levin machines: choice-cell initialization after independent computations
ProvedCookLevin.machine_choice_cells_from_bankscomplexitycook-levinloopsturing-machines
Initialize the tape-index-dependent counter and emit the exact certificate-choice formula at a fixed arbitrary logical tape index from two computed bound tapes. Preserve both saved work banks and produce canonical output with the explicit runtime bound.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_choice_cells_from_banks {a b G : Nat} (hG : 4 ≤ G) (alphabet j : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (a + b + 5) G R ∧
∀ (sh : Shape) (m : Nat) (input : Tape) (fuel : Nat → Symbol) (left right : List Tape),
sh.G = alphabet → left.length = a → right.length = b → fuel 0 ≠ oneSymbol →
(∀ p, p < sh.T + 1 → fuel (1 + p) = oneSymbol) →
fuel (1 + (sh.T + 1)) ≠ oneSymbol →
let n := sh.T + 1
let v := 8 * alphabet * (n + (n + 1) * j) + 1
let output := encodeFormula ((List.range n).map fun p =>
(reductionInit [] m 1 p).map fun s => Literal.Pos (sh.cellVar 0 j p s))
Transforms R
(input :: (left ++ (fuel, 0) :: (contents (List.replicate m oneSymbol), 0) ::
(right ++ [(contents [], 0), (contents [], 0)])))
(n * (A * v + B + 8 * alphabet * j + 9) + 8 * alphabet * j + 10)
(input :: (left ++ (fuel, 1 + n) :: (contents (List.replicate m oneSymbol), n) ::
(right ++ [(contents (boolsToSymbols (List.replicate v true)), 1 + v),
(contents (boolsToSymbols output), 1 + output.length)]))) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.