Cook–Levin machines: input-cell initialization and head advance
ProvedCookLevin.machine_emit_input_cell_bodycomplexitycook-levinloopsturing-machines
Emit the exact positive cell literal selected by the scanned input symbol, for symbols zero through three. Preserve input contents, advance the input head and unary cell counter. Runtime is affine in the literal base.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_input_cell_body {k G : Nat} (hk : 3 ≤ k) (hG : 4 ≤ G)
(alphabet : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (j p : Nat) (input : Nat → Symbol)
(bits : List Bool) (saved : List Tape),
sh.G = alphabet → saved.length + 3 = k → input p < 4 →
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 [literalN (.Pos (sh.cellVar 0 j p (input p)))]
Transforms R
((input, p) :: (contents (boolsToSymbols (List.replicate a true)), 1 + a) ::
(contents (boolsToSymbols bits), 1 + bits.length) :: saved)
(A * a + B)
((input, p + 1) :: (contents (boolsToSymbols (List.replicate a' true)), 1 + a') ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) :: saved) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.