Cook–Levin machines: input-cell formula from a computed width bank
ProvedCookLevin.machine_input_cells_from_bankcomplexitycook-levinloopsturing-machines
Emit the complete input-cell initialization formula from a unary tableau width tape and two blank tapes after an arbitrary saved work bank. Preserve input contents and the work bank, consume the width fuel, and produce canonical output. Runtime includes all initialization and final encoding markers.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_input_cells_from_bank {a G : Nat} (hG : 4 ≤ G) (alphabet : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (a + 4) G R ∧
∀ (sh : Shape) (input fuel : Nat → Symbol) (saved : List Tape),
sh.G = alphabet → saved.length = a →
(∀ p, p < sh.T + 1 → input p < 4) →
(∀ 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 + 1
let output := encodeFormula ((List.range n).map fun p =>
[Literal.Pos (sh.cellVar 0 0 p (input p))])
Transforms R
((input, 0) :: (saved ++ [(fuel, 0), (contents [], 0), (contents [], 0)]))
(n * (A * v + B + 3) + 6)
((input, n) :: (saved ++ [(fuel, 1 + n),
(contents (boolsToSymbols (List.replicate v true)), 1 + v),
(contents (boolsToSymbols output), 1 + output.length)])) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.