Cook–Levin machines: emit the head formula from a prepared fuel bank
ProvedCookLevin.machine_head_clause_emitter_from_fuel_bankcomplexitycook-levinloopsturing-machines
Initialize the counters and comparison flag, and emit exactly encodeFormula(headClauses sh) from three unary fuels at the end of a preserved work bank. All eight active work heads initially equal zero. Preserve both position fuels, consume time fuel, and leave the formula on the final tape. Runtime n*(tapesn^2(A*(2*a+c)+B)+3)+19.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_head_clause_emitter_from_fuel_bank {v G : Nat} (hG : 4 ≤ G) (tapes : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (v + 9) G R ∧
∀ (sh : Shape) (input : Tape) (times inner outer : Nat → Symbol) (saved : List Tape),
sh.k = tapes → saved.length = v →
inner 0 ≠ oneSymbol → outer 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → inner (1 + i) = oneSymbol) →
(∀ i, i < sh.T + 1 → outer (1 + i) = oneSymbol) →
inner (1 + (sh.T + 1)) ≠ oneSymbol → outer (1 + (sh.T + 1)) ≠ oneSymbol →
(∀ i, i < sh.T + 1 → times (1 + i) = oneSymbol) →
times (1 + (sh.T + 1)) ≠ oneSymbol →
let n := sh.T + 1
let a := 8 * sh.P * tapes * n + 2
let c := 8 * sh.P * tapes * n + 3
let output := encodeFormula (headClauses sh)
Transforms R
(input :: (saved ++ [(times, 0), (inner, 0), (outer, 0),
(contents [], 0), (contents [], 0), (contents [], 0), (contents [], 0), (contents [], 0)]))
(n * (tapes * (n^2 * (A * (a + a + c) + B)) + 3) + 19)
(input :: (saved ++ [(times, 1 + n), (inner, 1), (outer, 1),
(contents (boolsToSymbols (List.replicate a true)), 1 + a),
(contents (boolsToSymbols (List.replicate a true)), 1 + a),
(contents (boolsToSymbols (List.replicate c true)), 1 + c),
(contents (boolsToSymbols [true]), 1),
(contents (boolsToSymbols output), 1 + output.length)])) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.