Cook–Levin machines: transition commands block
ProvedCookLevin.machine_transition_next_counters_from_positionscomplexitycook-levinloopsturing-machines
Construct the initial next-time head and cell literal counters at physical tapes 4 and 5 from a reusable unary width fuel. The counters incorporate the exact tableau radix n+2; input, other tapes and fuel are preserved with an explicit linear runtime.
Preamble
import Definitions.Def_CookLevin_Reduction import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_transition_next_counters_from_positions {k G : Nat} (hk : 8 ≤ k)
(hG : 4 ≤ G) (tapes symbols : Nat) :
∃ R : Machine, TuringMachine k G R ∧
∀ (n : Nat) (input state readBase head out : Tape) (fuel : Nat → Symbol) (saved : List Tape),
fuel 0 ≠ oneSymbol →
(∀ i, i < n → fuel (1 + i) = oneSymbol) →
fuel (1 + n) ≠ oneSymbol →
let c := 8 * tapes * (n + 2) + 3
let e := 8 * symbols * tapes * (n + 2) + 1
Transforms R
(input :: state :: readBase :: head :: (contents [], 1) :: (contents [], 1) :: out :: (fuel, 1) :: saved)
(16 * tapes + 16 * symbols * tapes + 8 + n * (8 * tapes + 8 * symbols * tapes + 6))
(input :: state :: readBase :: head ::
(contents (boolsToSymbols (List.replicate c true)), 1 + c) ::
(contents (boolsToSymbols (List.replicate e true)), 1 + e) ::
out :: (fuel, 1) :: saved) := by sorrySource
Transition-clause emission for the Cook–Levin reduction.