Other people have noted that Solomonoff log-probability differs from Kolmogorov complexity only by a constant. But there’s another similar pair of objects I’m interested in, where I don’t know whether the analogous claim holds. Namely, in my original definition of the AIT intelligence measure, I used Kolmogorov complexity, because I implicitly assumed it’s the same as Solomonoff log-probability up to a constant. But Alex questioned this claim, which is why I switched to Solomonoff log-probability when writing about the physicalist version (see Definition 1.6 here). The crucial difference between this and the question in the OP is, we’re looking at programs selected by Solomonoff-expectation of something-to-do-with-their-ouput, rather than directly by their output (which places us on different spots on the computability ladder). If the two are different then I’m pretty sure Solomonoff log-probability is the correct one, but are they? I would be very interested to know.
It’s not differing by a constant, at least in some situations.
Here’s interstice’s comment below, reproduced:
I only just realized that you’re mainly thinking of the complexity of semimeasures on infinite sequences, not the complexity of finite strings. I guess that should have been obvious from the OP; the results I’ve been citing are about finite strings. My bad! For semimeasures, this paper proves that there actually is a non-constant gap between the log-total-probability and description complexity. Instead the gap is bounded by the Kolmogorov complexity of the length of the sequences. This is discussed in section 4.5.4 of Li&Vitanyi.
Other people have noted that Solomonoff log-probability differs from Kolmogorov complexity only by a constant. But there’s another similar pair of objects I’m interested in, where I don’t know whether the analogous claim holds. Namely, in my original definition of the AIT intelligence measure, I used Kolmogorov complexity, because I implicitly assumed it’s the same as Solomonoff log-probability up to a constant. But Alex questioned this claim, which is why I switched to Solomonoff log-probability when writing about the physicalist version (see Definition 1.6 here). The crucial difference between this and the question in the OP is, we’re looking at programs selected by Solomonoff-expectation of something-to-do-with-their-ouput, rather than directly by their output (which places us on different spots on the computability ladder). If the two are different then I’m pretty sure Solomonoff log-probability is the correct one, but are they? I would be very interested to know.
It’s not differing by a constant, at least in some situations.
Here’s interstice’s comment below, reproduced:
Link to the paper is below:
https://www.cs.bu.edu/faculty/gacs/papers/Gacs81.pdf