Cook–Levin machines: choice-cell scan at an arbitrary tape index
ProvedCookLevin.machine_emit_choice_cells_from_countercomplexitycook-levinloopsturing-machines
Emit the exact ordered certificate-choice clause chunk at any logical tape index over a bounded position range, preserving the actual input and saved work bank.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_emit_choice_cells_from_counter {k G : Nat} (hk : 5 ≤ k) (hG : 4 ≤ G)
(alphabet : Nat) :
∃ R : Machine, ∃ A B : Nat, TuringMachine k G R ∧
∀ (sh : Shape) (j m n : Nat) (input : Tape) (fuel : Nat → Symbol)
(bits : List Bool) (saved : List Tape),
sh.G = alphabet → saved.length + 5 = k →
(∀ p, p < n → fuel (1 + p) = oneSymbol) → fuel (1 + n) ≠ oneSymbol →
let a₀ := literalN (.Pos (sh.cellVar 0 j 0 0))
let aₙ := literalN (.Pos (sh.cellVar 0 j n 0))
let chunk := (List.range n).flatMap fun p => 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), 0) :: (fuel, 1) :: saved)
(n * (A * aₙ + B + 3) + 1)
(input :: (contents (boolsToSymbols (List.replicate aₙ true)), 1 + aₙ) ::
(contents (boolsToSymbols (bits ++ chunk)), 1 + (bits ++ chunk).length) ::
(contents (List.replicate m oneSymbol), n) :: (fuel, 1 + n) :: saved) := by sorrySource
Input-dependent initialization for the Cook–Levin reduction.