xu-2024-inevitability-theorem-core
IN premise — summaries/2026/08/24/xu-2024-hallucination-innate-sA-appendix.md
Created 2026-08-24T17:11:29+00:00
For all computable LLMs h, there exists a computable linear ordering < on finite strings such that h hallucinates on the question 's_{2n+1} < s_{2n}?' regardless of how many training samples are provided (Xu et al. 2024).
Summary
No matter how much data you feed a language model, you can always construct a specific pattern of comparisons where the model will answer incorrectly, and no amount of additional training will fix it. This means hallucination is not just a bug that more data or better tuning can eliminate; it is a hard mathematical ceiling on what any computable model can guarantee, so systems built on LLMs must assume occasional errors are unavoidable rather than treat them as failures to be engineered away.