Operational oracle cost equals the number of oracle-query steps
ProvedCountingLLL.ReciprocalTest.oracle_cost_eq_query_stepsalgorithmsprobability
For every entropy tape, the full operational ReciprocalTest oracle cost equals the extended-nonnegative count of steps whose phase is an oracle query. On a nonhalting tape both quantities are infinite. This connects the operational cost observable to finite-time state probabilities.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open MeasureTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.oracle_cost_eq_query_steps (ω : Entropy) :
oracleCost ω = ∑' t, (match (run ω t).phase with | .coinOracle _ => (1:ℝ≥0∞) | _ => 0) := 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