The claim of the paper is that computation is irreducible (assuming P!=NP), LLMs have limited computational capacity and will hallucinate on the irreducible problems.

I don’t know, the claim seems dubious to me. We usually are able to have algorithms that return a failure status, when the problem proved to be too large. Avoiding the “hallucination”. Don’t see why LLMs can’t have that embedded.