Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Kolmogorov Complexity - it's a bit silly

forwardscattering.org

Post reply on HN
Print view View original

31–39 of 39 posts

Re: Kolmogorov Complexity - it's a bit silly

#31

Post by Houshalter »

bo1024 wrote: post #28

The post has an incorrect definition of Kolmogorov Complexity. It says: > The overall Kolmogorov complexity of a string is thus defined as K(x)=|p| where p is the shortest program string for language L such that L(p)=x and we consider all programming languages. This is wrong. The definition of Kolmogorov complexity is always given relative to some fixed programming language. For example, K_perl or K_ruby are just fin…

The website is down so I have no idea what his argument is, but when I studied the concept I found it alarming they just handwave away the issue that it depends what Turing machine you use. There's no reason the constant can't be arbitrarily huge.

Re: Kolmogorov Complexity - it's a bit silly

#32

Post by Houshalter »

mappum wrote: post #15

The author misses the point that Kolmogorov Complexity isn't meant to be used as a practical measurement, but is just a theoretical way to think about information. There is no way to measure a string's "Kolmogorov Units", but you can just generally agree that "abababababababababababababababababababab" is less complex than "ababaaabbabaabaababbbabaababbbaaababbbba". If you really wanted a practical standard measure, t…

The problem the author is hitting on is that there isn't any standard language you can use. Every language will express some things better and other things worse.

This is a philosophical problem in how we should do induction. It's also a practical one in creating artificial intelligence.

Re: Kolmogorov Complexity - it's a bit silly

#33

Post by cma »

Houshalter wrote: post #31
bo1024 wrote: post #28

The post has an incorrect definition of Kolmogorov Complexity. It says: > The overall Kolmogorov complexity of a string is thus defined as K(x)=|p| where p is the shortest program string for language L such that L(p)=x and we consider all programming languages. This is wrong. The definition of Kolmogorov complexity is always given relative to some fixed programming language. For example, K_perl or K_ruby are just fin…

The website is down so I have no idea what his argument is, but when I studied the concept I found it alarming they just handwave away the issue that it depends what Turing machine you use. There's no reason the constant can't be arbitrarily huge.

As long as arbitrarily huge is finite it doesn't really affect the usefulness of kolmogorov complexity.

Re: Kolmogorov Complexity - it's a bit silly

#34

Post by Houshalter »

codeflo wrote: post #22

An analogy: there are multiple calendar systems in widespread use. Each one of those defines a different year 0. In fact, how I define time 0 is completely arbitrary, so that for any given moment in time, I can define a calendar system that defines this moment to be exactly 00:00:00 on day 1 of year 0 in my new calendar system. From this fact, using the logic of the article, I can show that any moment is time 0 (in s…

It's more like each calendar system maps the time to some completely arbitrary function. So in one calendar system, the number of years between 2000 and 2014 is 14 years, and the distance between 1990 and 1991 is 1,000 years.

But at least with calendars it might be manageable. We want to do operations like find the lowest number of bits needed to represent some data, or to do comparisons between the complexity of different strings. If this varies based on the programming language you use, then it's problematic at the very least.

Re: Kolmogorov Complexity - it's a bit silly

#35

Post by marris »

The author is not including the machine size.

From wikipedia:

"We could, alternatively, choose an encoding for Turing machines, where an encoding is a function which associates to each Turing Machine M a bitstring . If M is a Turing Machine which, on input w, outputs string x, then the concatenated string w is a description of x. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally preferred in the research literature. In this article, an informal approach is discussed."

If you consider the length of the Turing machine and the input string, then your don't get K = 0. The author's approach only includes the size of w, which is always 0.

How big are the machines used by the author's silly approach? If we wanted to describe the machine that prints "abababababbaba", we could write the program/specification as:

(1) Use the machine L_silly_abababababbaba (2) Use the string ''

How can we encode this into a shorter program/specification? Maybe by concatenating the machine name and ''?

L_silly_abababababbaba ''

Or we can be clever and realize that the string is always '' so we just need to machine name

L_silly_abababababbaba

Or we can say we don't need the L_silly_

abababababbaba

Can we go shorter? What if we specify a gzipped version of the string? We can take the string, unzip it, and use that Turing machine. But most strings are not compressible via gzip. So there will be many strings for which the shortest program via this approach is:

abababababbaba

... and some of the other words in this posted comment...

Re: Kolmogorov Complexity - it's a bit silly

#36

Post by bo1024 »

Houshalter wrote: post #31
bo1024 wrote: post #28

The post has an incorrect definition of Kolmogorov Complexity. It says: > The overall Kolmogorov complexity of a string is thus defined as K(x)=|p| where p is the shortest program string for language L such that L(p)=x and we consider all programming languages. This is wrong. The definition of Kolmogorov complexity is always given relative to some fixed programming language. For example, K_perl or K_ruby are just fin…

The website is down so I have no idea what his argument is, but when I studied the concept I found it alarming they just handwave away the issue that it depends what Turing machine you use. There's no reason the constant can't be arbitrarily huge.

If it helps any, the concept of KC is so impractical that this is probably the least of our worries.... The main important thing is that any theorem you prove will hold no matter which programming language/Universal TM you choose.

Re: Kolmogorov Complexity - it's a bit silly

#37

Post by Houshalter »

cma wrote: post #33
Houshalter wrote: post #31

Earlier quoted context omitted.

The website is down so I have no idea what his argument is, but when I studied the concept I found it alarming they just handwave away the issue that it depends what Turing machine you use. There's no reason the constant can't be arbitrarily huge.

As long as arbitrarily huge is finite it doesn't really affect the usefulness of kolmogorov complexity.

How doesn't it? It makes it completely impractical to use because the complexity you get for any string is entirely dependent on the language you use. We have no way of deriving what function set the universe uses from first principles.

Re: Kolmogorov Complexity - it's a bit silly

#38

Post by cma »

Houshalter wrote: post #37
cma wrote: post #33

Earlier quoted context omitted.

As long as arbitrarily huge is finite it doesn't really affect the usefulness of kolmogorov complexity.

How doesn't it? It makes it completely impractical to use because the complexity you get for any string is entirely dependent on the language you use. We have no way of deriving what function set the universe uses from first principles.

Just as for any finite string you chose you can chose a finite language L to trivially produce it, for any finite language L you chose, you can chose a finite string S that can't be trivially produced. If you chose L such that it trivially covers the structures of one universe (or a finite number of universes), there are infinite other universes in the same class of complexity which it doesn't cover.

Re: Kolmogorov Complexity - it's a bit silly

#39

Post by Houshalter »

cma wrote: post #38
Houshalter wrote: post #37

Earlier quoted context omitted.

How doesn't it? It makes it completely impractical to use because the complexity you get for any string is entirely dependent on the language you use. We have no way of deriving what function set the universe uses from first principles.

Just as for any finite string you chose you can chose a finite language L to trivially produce it, for any finite language L you chose, you can chose a finite string S that can't be trivially produced. If you chose L such that it trivially covers the structures of one universe (or a finite number of universes), there are infinite other universes in the same class of complexity which it doesn't cover.

I'm not sure if you are disagreeing with me or not. The problem is that we have no idea what language or metalanguage we should start with.
Post reply on HN