Cook–Levin machines: complete halt formula from counters
ProvedCookLevin.machine_halt_clause_emitter_from_counterscomplexitycook-levinloopsturing-machines
Emit exactly encodeFormula(haltClauses sh) from prepared counters and two unary fuels, restoring position fuel after every time slice and including the formula terminator.
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_counters {k G : Nat} (hk : 9 ≤ k)
(hG : 4 ≤ G) (tapes symbols states : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (input : Tape) (positions times : Nat → Symbol) (saved : List Tape),
sh.k = tapes → sh.G = symbols → sh.Q = states → saved.length + 9 = k →
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 :: (contents (boolsToSymbols (List.replicate (8 * states + 4) true)), 1 + (8 * states + 4)) ::
(contents (boolsToSymbols (List.replicate (2) true)), 1 + (2)) ::
(contents (boolsToSymbols (List.replicate (8 * sh.P * tapes + 3) true)), 1 + (8 * sh.P * tapes + 3)) ::
(contents (boolsToSymbols (List.replicate (0) true)), 1 + (0)) ::
(contents (boolsToSymbols (List.replicate (8 * symbols * sh.P * tapes + 1) true)), 1 + (8 * symbols * sh.P * tapes + 1)) ::
(contents [], 1) :: (positions, 1) :: (times, 1) :: saved)
(n * ((tapes + 1) * ((sh.T + 1) * (A * (a + b + c + d + e) + B + 6) + 4 + (16 + 16 * symbols)) + 8 * (states + 1) + 3) + 2)
(input :: (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) ::
(positions, 1) :: (times, 1 + n) :: saved) := by sorrySource
Compose the five-counter template compiler, fixed counter strides and reusable unary iteration with the actual halt-clause encoding.