If reality has irreducible randomness (an open question afaik), and we're talking about theories and explanations (so we're not necessarily trying to describe the actual state of every particle in the universe, but only the rules governing their interactions), couldn't we have a complete, correct theory that was much smaller than the universe and contained terms for the random elements?
There would always be the possibility that it would turn out to be wrong, but it could be complete and correct, so it seems like the original claim must depend heavily on the word 'provable' and not on the impossibility of describing a system via a map smaller than the territory.
edit: but also, surely 'the territory is randomized' is a contingent physical fact, and not a necessary truth of information theory. Until we know for sure that there is irreducible randomness, we can't know that the information content of the universe (including the actual state of all particles at all times) isn't losslessly compressible, right?