Fresh-coordinate simulation of the fully suppressed execution
ProvedCountingLLL.ReciprocalTest.suppressed_reveal_fresh_simulationformalizationprobability
The reveal-machine encoding exactly simulates every finite step of the fully suppressed operational execution on the encoded entropy tape. Moreover, every coordinate selected by this encoded machine is absent from its set of previously revealed coordinates. In particular, suppressed checks are conservatively recorded as reads, so this freshness applies to all later oracle and fair-bit queries.
Preamble
import Definitions.Def_CountingLLL_ReciprocalSuppressedReveal open CountingLLL.ReciprocalTest CountingLLL.RevealMachine
Formal statement
theorem CountingLLL.ReciprocalTest.suppressed_reveal_fresh_simulation :
(∀ (ω : Entropy) (n : ℕ),
(CountingLLL.RevealMachine.run suppressedRevealProgram (entropyCode ω) initial n).1 = allSuppressedRun ω n) ∧
(∀ (x : ReadIndex → ℕ) (n : ℕ) (a : ReadIndex),
readIndex (CountingLLL.RevealMachine.run suppressedRevealProgram x initial n).1 = some a →
a ∉ (CountingLLL.RevealMachine.run suppressedRevealProgram x initial n).2) := by sorrySource
Liu, Wang, Yin, Zhang, Zhou, A Counting and Sampling Lovász Local Lemma, STOC submission #442, §6.2, Lemma 6.5; adaptive suppressed-execution coupling.