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 demonstrate that this goal is fundamentally unattainable. Godel's theorems establish that no theory based on computational algorithms can be both complete and consistent, while Tarski's undefinability theorem demonstrates that even within quantum gravity, or any computational framework, a fully consistent internal determination of true propositions is impossible. Chaitin's incompleteness theorem further reinforces this conclusion, revealing intrinsic limits to any computational theory. We discuss some possible consequences for descriptions of physical systems, and note that a non-algorithmic approach should be essential for any theory of everything.