However, their argument rely on that ”quantum gravity” is what makes the universe uncomputable. I’m not sure how valid this statement is.

Here is the assumption the authors use that brings quantum gravity into the proof:

As we do not have a fully consistent theory of quantum gravity, several different axiomatic systems have been proposed to model quantum gravity [26–32]. In all these programs, it is assumed a candidate theory of quantum gravity is encoded as a computational formal system F_QG = {L_QG, ΣQG, R_alg} .

I interpret their assumption to mean that describing quantum gravity in this way is how it would be defined as a formal computational system. This is the approach that all of the other leading theories (String Theory, Loop Quantum Gravity) have taken, which have failed to provide a fully consistent and complete description of gravity. I think the proof is saying that non-computational components can be incorporated into a fully consistent and complete formal system and so taking a non-computational approach to quantum gravity would then incorporate gravity into the formal system thereby completing the theory of everything.

Does that make sense? I am not a logician by any extent and I have no idea how robust this proof really is. I do think the bold claims the authors are making deserve heavy scrutiny, but I am not the one to provide that scrutiny.