Do you necessarily need to compute anything in order to perform a simulation? Suppose whenever some weird undecidable statement quantum gravity situation comes up inside the simulation, you pause it, recreate the scenario on a lab bench, and then copy the data into your simulation. You didn't compute what would happen, you don't even necessarily understand how it works, but as long as its the same quantum gravity stuff inside and out, the simulation can proceed faithfully. This makes some assumptions about locality I guess.
Of course the whole affair seems a little moot since you obviously only have to be accurate enough that it doesn't disrupt the ancestor simulation or whatever, but that's less fun to think about I suppose.