Can quantum gravity be both consistent and complete?

General relativity, despite its profound successes, fails as a complete theory due to presence of singularities. While it is widely believed that quantum gravity has the potential to be a complete theory, in which spacetime consistently emerges from quantum degrees of freedom through computational algorithms, we argue that this goal could be fundamentally unattainable. We examine how this limitation could emerge in various contexts, depending on whether or not every mathematically valid result is physically realized. In the first case, Gödel’s incompleteness theorems, along with related results by Tarski and Chaitin, imply that no theory formulated as a formal axiomatic system can be complete, and that within any computational framework, a fully consistent internal truth predicate is impossible. In the second case, if only a subset of mathematical truths is realized in nature, we argue that this selection cannot be determined by any purely computational process. Hence, a meta-theoretical approach based on nonalgorithmic understanding is indispensable in every case. We discuss some possible consequences of this observation for describing physical systems and note that a nonalgorithmic approach should be essential for any theory of everything.