xu-2024-theorem-e2-ce-set-bound

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

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

The set of ground-truth functions on which a computable LLM can be hallucination-free is a subset of a computably enumerable set of total computable functions, meaning functions outside this set (e.g., the halting problem) are fundamentally unreachable by any LLM.

Summary

There is a hard mathematical ceiling on the kinds of problems an LLM can ever answer without making errors, and that ceiling is defined by which well-behaved, always-terminating functions fall inside a specific countable collection. This is not an engineering gap that better data or more compute might close; it is provable that entire categories of questions, like determining whether an arbitrary program will ever halt, simply lie beyond what any computable language model can handle correctly.