Optimally compressed data is essentially indistinguishable from random noise. Could we tell the difference between a universe that has already been converted into computronium and one that's empty?

Optimally compressed data also has the highest possible entropy (each bit is maximally informative), so that's how a universe being used as computronium would look. So we're not in such a universe, since:

a) It has too many observable regularities (i.e. we can and do further compress it by identifying laws of physics)
b) black holes have the highest entropy per unit mass, and most of the universe isn't one.
c) ETA: entropy manages to keep increasing, so it can't be at a maximum