I think its uncomputability already does that. When you make a computable version by limiting attention to some framework of descriptive capabilities smaller than universal computation, different choices of that framework will give you different measures of simplicity. What is simple in one framework may seem elaborate and baroque in another. Or as some military strategist once put it: "To the foot-soldier, the strategy of a general may seem obscure, shrouded in shadows and fog, but to the general himself, his way is as plain as if he were marching his army down a broad, straight highway."

Consider this alternative characterization. Someone wants to fit a polynomial to some data. They pre-selected a sparse set of polynomials, which are in general ridiculously complex. Against all odds, they get a good fit to the training data. This theorem says that, because they haven't examined lots and lots of polynomials, they definitely haven't fallen into the trap of overfitting. Therefore, the good fit to the training data can be expected to generalize to the real data. Shalizi is saying that this story is fine as far as it goes - it's just not Occam's Razor.