Finite machine execution depends only on the coordinates read
ProvedCountingLLL.RevealMachine.run_depends_on_seenalgorithmsprobability
For a deterministic machine that reads at most one array coordinate per step, suppose two input arrays agree on every coordinate read by the first execution during its first steps. Then the two executions have identical program states and identical sets of read coordinates after those steps.
Preamble
import Definitions.Def_CountingLLL_RevealMachine open CountingLLL.RevealMachine
Formal statement
theorem CountingLLL.RevealMachine.run_depends_on_seen {σ ι α : Type*} [DecidableEq ι] (P : Program σ ι α)
(ω ω' : ι → α) (initial : σ) (n : ℕ)
(h : ∀ i ∈ (run P ω initial n).2, ω i = ω' i) :
run P ω initial n = run P ω' initial n := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, Algorithm 6, pp. 27–28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf