# DanielLC comments on What is the advantage of the Kolmogorov complexity prior? - Less Wrong

12 16 February 2012 01:51AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Best

You are viewing a single comment's thread.

Comment author: 16 February 2012 06:19:36AM 0 points [-]

Maybe there is some true randomness in the universe

Not a problem. Suppose you flip a quantum coin ten times. If you record the output, the K-complexity is ten bits. As such, there's a 1/1024 prior probability of getting that exact output. This is exactly what you'd get if you assumed it was random.

Basically, K-complexity is treating the very laws of physics as random. Any randomness on top of that works the same way as it would as part of that.

The problem is that it seems that things that are definable but not computable should be above random chance. For example, the K-complexity of a halting oracle is infinite, but it can be defined in finite space. Would the probability of the fine structure constant being a halting oracle be infinitesimal?

One reason to use K-complexity is that so far, it's worked far better than anything else. As far as we know, we can fit the laws of physics on a note card, yet the universe contains well over 10^80 particles, and don't get me started on the amount of computing power necessary to run it.

Comment author: 16 February 2012 01:18:17PM *  1 point [-]

Basically, K-complexity is treating the very laws of physics as random.

Assuming a lawful universe, doing the distibution per algorithm is better than per universe. But there are many possibilities how to do the distribution per algorithm. Even selecting a different (Turing-complete) programming language provides a different K-complexity.

As I understood the question in the article, if we already do the distribution per algorithm, the only necessary thing is to give a nonzero starting probability to any algorithm. This is enough; the Bayesian updates will then make the following predictions more reliable.

So the question is: assuming that we give nonzero prior probability to any algorithm:

• a) is there any advantage in using Kolmogorov complexity? or
• b) are in some sense all other priority distributions just variants of K-complexity? or
• c) something else...?
Comment author: 16 February 2012 08:51:40AM *  0 points [-]

Maybe there is some true randomness in the universe

Not a problem.

I know it's not a problem. I explained exactly how to modify Solomonoff induction to handle universes that are generated randomly according to some computable law, as opposed to being generated deterministically according to an algorithm.

Suppose you flip a quantum coin ten times. If you record the output, the K-complexity is ten bits.

Maybe it is, maybe it isn't. Maybe your definition of Kolmogorov complexity is such that the Kolmogorov complexity of every string is at least 3^^^3, because you defined Kolmogorov complexity using a really dumb universal machine. Maybe it's 2, because you programmed a universal machine that was really good at compressing the string 0101110010, because you like it, and it so happens that was what you flipped. If you flip a coin a very large number of times, it's very likely that the Kolmogorov complexity of the output is at least the number of flips, but it could be much smaller due to chance.

As such, there's a 1/1024 prior probability of getting that exact output. This is exactly what you'd get if you assumed it was random.

False, because you don't actually know the complexity was 10.

Basically, K-complexity is treating the very laws of physics as random. Any randomness on top of that works the same way as it would as part of that.

No, it's not doing that at all. Using a complexity-weighted prior is assuming that the universe follows some random computable law, which is more likely to be simple than complex. I suppose this is true to the extent that any probability distribution on a countable set vanishes in the limit (for any enumeration of the countable set!), but I see no reason to bring Kolmogorov complexity into it.

The problem is that it seems that things that are definable but not computable should be above random chance. For example, the K-complexity of a halting oracle is infinite, but it can be defined in finite space. Would the probability of the fine structure constant being a halting oracle be infinitesimal?

I have no idea how to make sense of this question. Are infinitely many bits of fine structure constant even physically meaningful? If beyond a certain point of precision, the fine structure constant can't be measured even in principle because it has no detectable physical effects on accessible time/space scales, it makes no sense to even have an answer to the question "is the fine structure constant a halting oracle?" let alone the probability of such an event.

One reason to use K-complexity is that so far, it's worked far better than anything else. As far as we know, we can fit the laws of physics on a note card, yet the universe contains well over 10^80 particles, and don't get me started on the amount of computing power necessary to run it.

I'll grant you that Occam's razor works well in science. That wasn't the question. The question is what is the advantage, if any, of starting with a Kolmogorov prior for Solomonoff induction, as opposed to any other arbitrary prior. You haven't answered my question.

Comment author: 16 February 2012 10:15:28PM 0 points [-]

As far as we know, we can fit the laws of physics on a note card, yet the universe contains well over 10^80 particles, and don't get me started on the amount of computing power necessary to run it.

But you can't fit a description of the current state of those particles on a note card, which you would need in order to actually make predictions.

Comment author: 17 February 2012 03:45:29AM 0 points [-]

The laws of physics, combined with the initial conditions of the universe, is sufficient to describe the state of all the particles for all eternity.

We don't really have much of an idea of what the initial conditions are, but there's no reason to believe that they're complicated.

Comment author: 17 February 2012 03:54:53AM 0 points [-]

but there's no reason to believe that they're complicated.

Are there any reasons to believe they're not complicated that don't rely on assuming a K-complexity prior?

Comment author: 17 February 2012 05:24:59AM 0 points [-]

No, nor is there a reason to assume that anything else we don't know about physics isn't complicated.

That being said, the probability that even just the parts we know are so simple by coincidence is vanishingly small.

Comment author: 17 February 2012 06:52:13PM 0 points [-]

That being said, the probability that even just the parts we know are so simple by coincidence is vanishingly small.

Not when you realize that the parts we know are the parts that were simple enough for us to figure out.

Comment author: 17 February 2012 07:19:26PM 0 points [-]

No, they're the parts that are obvious enough to figure out. If there was something complicated that made a big difference, we'd have noticed it, and just not figured it out. The parts that we don't understand are parts that make such a tiny difference that they can't properly be experimented with.

Comment author: 19 February 2012 05:42:12PM *  1 point [-]

This kind of depends on what you mean by “big difference” and “complicated enough”.

For example, I can see humanity not yet detecting that spontaneous fission isn’t random but decided by a really good random number generator.

One might also imagine a ridiculously complicated program that makes elementary particles appear to behave randomly, except that when a huge number of such particles are “assembled” in a strange loop of sufficient complexity to be considered “a human-level self-aware entity” the pseudo-random micro-behavior leads to powerful effects at the macro-scale. Pretty much anything about what brains do that we don’t yet understand in detail could be hypothesised to arise from this. (I.e., the gods jiggle the dice to make humans, e.g., risk-adverse. Or send hurricanes towards groups of people who aren’t capitalist enough, whatever.)

Of course, such hypotheses are very complex and we’d usually say that it’s unreasonable to contemplate them. But using Occam’s razor would be circular in this particular thread.

Comment author: 19 February 2012 08:17:23PM 0 points [-]

For example, I can see humanity not yet detecting that spontaneous fission isn’t random but decided by a really good random number generator.

There are infinitely many possible realities that look simple to program but aren't, but most complicated realities don't look nearly this simple. The Copenhagen interpretation looks the same as Many Worlds, but that's because it was discovered while trying to figure out this reality, not because most possibilities do.

But using Occam’s razor would be circular in this particular thread.

But no alternative has been put forward where this is more likely, let alone one that gives nearly the probability of a reality that looks like this than Occam's razor does.

Comment author: 20 February 2012 06:56:29AM *  1 point [-]

But no alternative has been put forward where this is more likely, let alone one that gives nearly the probability of a reality that looks like this than Occam's razor does.

Well, yeah (I mean, there might have been, I just don’t know of any). Don’t get me wrong, I’m not arguing against Occam’s razor.

I just meant that you seem to have given the assertion “the probability that even just the parts we know [about physics] are so simple by coincidence is vanishingly small” as a not-quite-but-kind-of justification for Occam’s razor—even though just in the previous paragraph you said there’s no reason to think not-yet-known laws of physics aren’t complicated, the “that being said” seems to kind of contradict it—but to judge that the probability of a coincidence is small, or to say “most complicated realities don’t look this simple”, would need either Occam’s razor (simpler is likelier) or some kind of uniform prior (all possible realities are as likely, and there are more of the complicated-looking ones), or another alternative that hasn’t been put forward yet, as you say. Thus, the circularity.

If for some reason we thought that extremely complicated realities that simulate very simple rules at some scales are extremely more likely to observe than all others, then “the probability that even just the parts we know are so simple” would be large. I could see some anthropic argument for this kind of thing. Suppose we discover that conscious observers cannot exist in environments with too complicated behavior; then we’d expect to only see environments with simple behavior; but (with a “uniform prior”) there are vastly more complex systems that simulate simple behaviors within than simple ones. (For any simple behavior, there is an infinity of much more complicated systems that simulate it in a part of themselves.) Thus, under the “limit complexity for observers” hypothesis we should expect a few layers of simple rules and then an incomprehensibly complicated system they arise out of “by accident”.