One related idea of complexity is averaged fractal dimension over some range of scales. We might measure a 2d figure’s complexity (embedded in 3d) by how its box-counting dimension is greater than 2 over some relevant range of scales. But extending this analogy to models might require a better understanding of the average case of runtime / storage of the model vs. predictive accuracy in various environments (significantly better than that contained in this comment).
If we think of the environment as a turing machine of length (but not K-complexity, because simple models provide a path to reduce K-complexity) E, and the model as a turing machine of length M, M<E, then the average case is actually pretty simple, because things are not on average compressible. The average best model accuracy will (I think) just be around M/E. Things are modelable to the the extent that you can push your accuracy curve above this line. But this seems a little too centered on agent perception to be what you want.
Another thought is that one of your desiderata for application appears to be an interaction with local complexity—the universe may be K-simple, but parts of the universe will be K-complex. But it seems like you somehow want to start with the description of a universe and immediately have some quantification of how K-complex parts of it will be.
One related idea of complexity is averaged fractal dimension over some range of scales. We might measure a 2d figure’s complexity (embedded in 3d) by how its box-counting dimension is greater than 2 over some relevant range of scales. But extending this analogy to models might require a better understanding of the average case of runtime / storage of the model vs. predictive accuracy in various environments (significantly better than that contained in this comment).
If we think of the environment as a turing machine of length (but not K-complexity, because simple models provide a path to reduce K-complexity) E, and the model as a turing machine of length M, M<E, then the average case is actually pretty simple, because things are not on average compressible. The average best model accuracy will (I think) just be around M/E. Things are modelable to the the extent that you can push your accuracy curve above this line. But this seems a little too centered on agent perception to be what you want.
Another thought is that one of your desiderata for application appears to be an interaction with local complexity—the universe may be K-simple, but parts of the universe will be K-complex. But it seems like you somehow want to start with the description of a universe and immediately have some quantification of how K-complex parts of it will be.