Fixed-width word-RAM state invariant
ProvedKSATSingleFlip.Connect.wordRAM_word_invariantIn the candidate fixed-width word-RAM model, suppose every register and memory cell initially contains an unsigned -bit word. After any finite number of program steps, every register and memory cell still lies in . This verifies that the unit-cost machine does not silently grow unbounded integer values during execution.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_WordRAM
Formal statement
namespace KSATSingleFlip.Connect
/-- A valid word-RAM state remains valid under every bounded execution. -/
theorem wordRAM_word_invariant (program : WordRAMProgram) (w T : ℕ) (s : WordRAMState)
(hr : ∀ r, s.registers r < 2^w) (hm : ∀ a, s.memory a < 2^w) :
(∀ r, (wordRAMRun program w T s).registers r < 2^w) ∧
∀ a, (wordRAMRun program w T s).memory a < 2^w := by
sorry
end KSATSingleFlip.Connect
Source
Formalization choice for the runtime statements of Theorem 1.3, Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf. The paper does not specify this machine model.