Cook–Levin machines: choice-cell body at an arbitrary tape index
ProvedCookLevin.machine_emit_choice_cell_bodycomplexitycook-levinloopsturing-machines
Emit one certificate-choice clause at an arbitrary logical tape index, using the supplied literal counter. The unary bound selects start marker, three choices, or blank. Advance the bound head and literal counter together.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_choice_cell_body {k G : Nat} (hk : 4 ≤ k) (hG : 4 ≤ G)
(alphabet : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (j m p : Nat) (input : Tape)
(bits : List Bool) (saved : List Tape),
sh.G = alphabet → saved.length + 4 = k →
let a := literalN (.Pos (sh.cellVar 0 j p 0))
let a' := literalN (.Pos (sh.cellVar 0 j (p + 1) 0))
let chunk := true :: encodeListNat
(clauseN ((reductionInit [] m 1 p).map fun s => Literal.Pos (sh.cellVar 0 j p s)))
Transforms R
(input :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols bits), 1 + bits.length) ::
(contents (List.replicate m oneSymbol), p) :: saved)
(A * a + B)
(input :: (contents (boolsToSymbols (List.replicate a' true)), 1 + a') ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(contents (List.replicate m oneSymbol), p + 1) :: saved) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.