Determined but Unreachable: Cryptographic Barrier to Language Generation

Can examples determine a language while leaving the production of even one new word out of reach? We show that this happens exactly when one-way functions exist. With one-way functions, attaching to every word a statistically binding but computationally hiding commitment to the key of a pseudorandom-function graph gives an efficiently presented family in which one example determines the language except with probability $2^{-\Omega (n)}$, yet every efficient generator has negligible probability of producing an unseen valid word within any polynomial horizon. With exponentially secure primitives the barrier extends to total running time $2^{\Omega (n)}$, which is tight up to the constant in the exponent. For the converse we view a family through its sampling map, which sends a hidden description and coins to the examples: the posterior is the projection of the uniform measure on a fibre, and a point of the fibre whose language lies inside the target enumerates fresh words forever. Classical universal posterior sampling in the absence of one-way functions, stated jointly with the hidden target and padded across lengths, then yields efficient generators that match every generator allowed to draw posterior samples, at infinitely many lengths. Hence one-way functions exist if and only if posterior sampling helps generation, and hard instances for generation and for identification exist under the same condition. Since the Bayesian generator idealizes in-context learning as implicit posterior inference, the result also shows that this idealization can be computationally out of reach even when a single example suffices statistically.