Missing Shade of Blue
Posts: 62
Joined: Dec. 2008
|
Wesley,
I read the paper you cited. Thanks for pointing me to it. It was clear and informative. But I still don't see how the universal distribution shows I am wrong.
I said that for any two finite strings, there is no language-independent means of determining which has the greater Kolmogorov complexity. Let's take strings s1 = 1010101010.... and s2 = 1000110111.... (where the ellipses indicate the strings are a billion digits long). I can construct a UTM for which the program to produce s1 will be shorter than the program to produce s2. In fact, my laptop is one such UTM.
But I can also construct a UTM for which s2 can be produced by a shorter program. I merely make it part of the UTMs hardware that if the input begins with a 0, it immediately prints out s2 and halts. If its input begins with a 1 it moves on to the next symbol on the tape and proceeds to responds to the rest of the input the same way my laptop does. For this UTM s2 is less complex than s1.
This is a completely general scheme. I can do it with any two finite strings. And it doesn't violate the Invariance Theorem.
Now you suggested that the Universal Distribution would actually provide a language-independent way of deciding whether s1 is simpler than s2 or vice versa. But I don't see how this can be true. According to the paper you cited, the Universal Distribution assigns higher probabilities to strings with lower Kolmogorov complexities. So prior to figuring out what the Distribution will look like, we need to figure out what the complexities of the individual strings are. And there's no language-independent way to do that.
Depending on what UTM we use to make our judgments about complexity, the Universal Distribution will look different. If we use my laptop, s1 will have a higher probability than s2. If we use the baroque computer I constructed, s2 will have a higher probability.
Isn't this right? How does the Universal Distribution help me figure out whether s1 is simpler than s2 independent of the UTM used? I guess I was imagining some way of assigning a distribution not over the strings, but over the ensemble of all possible UTMs. Maybe if we moved up to that level, we can come up with some sense in which one of the strings is simpler (because its complexity is lower on "more" UTMs as determined by our measure). But that's not what the Universal Distribution is.
Anyway, it strikes me that the correct way to approach this problem is not to attempt to articulate a language-independent notion of simplicity but to acknowledge that the particular inductive bias of the evolutionary process sets a natural language. It happens to be a language that works well for the kinds of fitness landscapes we see in nature. Maybe we can come up with a deeper reason for this match between learning algorithm and fitness landscape (I think Zachriel was suggesting that it has something to do with them being made of the same stuff) but I don't even know if that's the kind of thing that needs special explanation. I feel the same way about this phenomenon as I do about the alleged fine tuning of our fundamental constants: "What are the alternatives and how in the world did you get a probability measure over them?" So, as I said before, I'm satisfied.
|
