xu-2024-unconditional-vs-pac-distinction

IN premise — summaries/2026/08/24/xu-2024-hallucination-innate-sA-appendix.md

Created 2026-08-24T17:11:30+00:00

Xu et al. 2024's hallucination impossibility result is unconditional—no computably enumerable set of LLMs is hallucination-free across all computable worlds—making it logically distinct from PAC unlearnability, which requires assumptions of bounded error rates and polynomial-time constraints.

Summary

Xu et al. 2024 proved that hallucination in language models is unavoidable in the most basic logical sense, without needing any assumptions about how much error is allowed or how much computation you get. That makes it a harder wall than the usual "you can't learn this within a polynomial-time budget" results people often cite, because no amount of clever algorithm design or error tolerances can sidestep it.