On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation

Abstract

Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimension characterizes stronger information-theoretic guarantees [RLT25]. Neither restricts per-output computation. The cumulative-mistake objective in mistake-bounded generation makes finite failure prefixes quantitative [KPR26], and a per-output query budget exposes their computational source. Polynomial-time algorithms are known for parities, conjunctions, and monotone functions with polynomially many maxterms [JKO26]. We ask whether information-theoretic ease can coexist with bounded-access computational hardness. Relative to a random oracle H, we answer yes by constructing a countable collection 𝒞* of infinite languages with Cdim(𝒞*) = 0. Almost surely on the same H, an unbounded generator makes zero mistakes on every target and every complete distinct enumeration. Yet, writing λ for the target-seed length, every fixed uniform generator G with poly(λ, i) oracle queries at output i has a constant c_G > 0 such that, for every sufficiently large λ, some target incurs more than 2^(c_G λ) expected mistakes within its first 2(⌈2^(c_G λ)⌉ + 1) canonical outputs. Infinite accidental agreement enables exhaustive search; sparse queries hide fresh target values. Thus, in the random-oracle model, zero-mistake information-theoretic generation coexists with a generator-dependent exponential lower bound on worst-case expected mistakes under polynomial-query access.