Cook–Levin: exact initialization clause decomposition
ProvedCookLevin.startClauses_reductionInit_splitcomplexitycook-levinloopsturing-machines
Exact decomposition of Cook–Levin initialization into state and head clauses, input-tape cells, certificate choices, and blank work tapes. Includes zero-tape and one-tape shapes without extra hypotheses.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.startClauses_reductionInit_split (sh : Shape) (xs : List Symbol) (m : Nat) :
startClauses sh (reductionInit xs m) =
[[Literal.Pos (sh.stateVar 0 0)]] ++
(List.range sh.k).map (fun j => [Literal.Pos (sh.headVar 0 j 0)]) ++
(if 0 < sh.k then (List.range (sh.T + 1)).map (fun p =>
[Literal.Pos (sh.cellVar 0 0 p (contents xs p))]) else []) ++
(if 1 < sh.k then (List.range (sh.T + 1)).map (fun p =>
(reductionInit [] m 1 p).map (fun s => Literal.Pos (sh.cellVar 0 1 p s))) else []) ++
(List.range (sh.k - 2)).flatMap (fun j => (List.range (sh.T + 1)).map (fun p =>
[Literal.Pos (sh.cellVar 0 (j + 2) p (contents [] p))])) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.