Cook–Levin machines: halt emitter from fuel bank
ProvedCookLevin.machine_halt_clause_emitter_from_fuel_bankcomplexitycook-levinloopsturing-machines
Emit the complete halt formula from two unary fuels and six blank work tapes at the end of an arbitrary preserved work bank, including counter initialization and an explicit runtime bound.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_halt_clause_emitter_from_fuel_bank {v G : Nat} (hG : 4 ≤ G) (tapes symbols states : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine (v + 9) G R ∧
∀ (sh : Shape) (input : Tape) (times positions : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → sh.Q = states → saved.length = v →
positions 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → positions (1 + i) = oneSymbol) →
positions (1 + (sh.T + 1)) ≠ oneSymbol →
(∀ i, i < sh.T → times (1 + i) = oneSymbol) →
times (1 + sh.T) ≠ oneSymbol →
let n := sh.T
let a := 8 * (states + 1) * n + 8 * states + 4
let b := 8 * sh.P * tapes * n + 2
let c := 8 * sh.P * tapes * (n + 1) + 3
let d := 8 * symbols * sh.P * tapes * n
let e := 8 * symbols * sh.P * tapes * (n + 1) + 1
let output := encodeFormula (haltClauses sh)
Transforms R
(input :: (saved ++ [(times, 0), (positions, 0), (contents [], 0),
(contents [], 0), (contents [], 0), (contents [], 0), (contents [], 0), (contents [], 0)]))
(n * ((tapes + 1) * ((sh.T + 1) * (A * (a + b + c + d + e) + B + 6) + 4 + (16 + 16 * symbols)) + 8 * (states + 1) + 3) +
(sh.T + 1) * (8 * tapes + 8 * symbols * tapes + 6) +
8 * tapes + 8 * symbols * tapes + 8 * states + 24)
(input :: (saved ++ [(times, 1 + n), (positions, 1),
(contents (boolsToSymbols (List.replicate a true)), 1 + a),
(contents (boolsToSymbols (List.replicate b true)), 1 + b),
(contents (boolsToSymbols (List.replicate c true)), 1 + c),
(contents (boolsToSymbols (List.replicate d true)), 1 + d),
(contents (boolsToSymbols (List.replicate e true)), 1 + e),
(contents (boolsToSymbols output), 1 + output.length)])) := by sorrySource
Compose the five-counter template compiler, fixed counter strides and reusable unary iteration with the actual halt-clause encoding.