2026/08/05 by Xiaoyu Li, Andi Han, Dai Shi +2
Computer Science · #cs.CC
arxiv created 2026/08/05 · arxiv updated 2026/08/06
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 C^⋆ of infinite languages with closure dimension zero. 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 polynomially many oracle queries in λ and the output index i has a constant cG>0 such that, for every sufficiently large λ, some target incurs more than 2cGλ expected mistakes within its first 2(\lceil 2cGλ\rceil+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.