4 ms·

> The original Kolmogorov complexity is for finite strings. I wrote "Kolmogorov complexity" not "original Kolmogorov complexity" so this isn't particularly rel

> The original Kolmogorov complexity is for finite strings. I wrote "Kolmogorov complexity" not "original Kolmogorov complexity" so this isn't particularly relevant. The application of the concept to the infinite string which represents pi is essentially trivial. > Plus, the program would need to store that for whichever special strings you choose you will use this function but for other ones not. That will be a giant table that is part of your program. I honestly can't parse this. > Pi, being almost random by every statistical measure, has as much information as a random string This is wrong. You can consider something like a simple communication task. Alice and Bob share a phone line and she is attempting to tell him a number. Every second the line allows her to send a bit to Bob. For a truly random number she has to use the line infinitely many times to tell him the number. To send pi she can send a finite number of bits which amount to a program to compute pi and he can do the computation on his end.

pishpash 3y ago
I urge you to go back and look at how Kolmogorov complexity is defined. It includes the notion that a program needs to decide whether to output the string directly or to generate it from some program. You're assuming Alice and Bob have already pre-synchronized what kind of computing machine is going to be used, one in which pi is the output of a relatively short program, as opposed to another type of machine where some other random-looking number has that property (random to you, pseudo-randomly generated via some machinery for all you know). You are assuming many things away. Also it is absolutely not trivial to extend Kolmogorov complexity to infinite strings. There are multiple formulations and they are a lot more difficult than for finite strings. Not the computation part but the complexity assignment part.
- eigenket 3y ago
  I agree there is a bunch of complexity in generalising Kolmogorov complexity to general infinite strings. However I'm not really trying to do that here, all I want is enough to back-up the statement I made before, that the complexity of pi is finite. Doing that is much more trivial than what you're talking about. Theres a bunch of fine detail in getting it down to defining an actual number measuring complexity which I don't care about at all, all I care about (in the context of this discussion) is that the number is finite.

pishpash 3y ago

I urge you to go back and look at how Kolmogorov complexity is defined. It includes the notion that a program needs to decide whether to output the string directly or to generate it from some program. You're assuming Alice and Bob have already pre-synchronized what kind of computing machine is going to be used, one in which pi is the output of a relatively short program, as opposed to another type of machine where some other random-looking number has that property (random to you, pseudo-randomly generated via some machinery for all you know). You are assuming many things away. Also it is absolutely not trivial to extend Kolmogorov complexity to infinite strings. There are multiple formulations and they are a lot more difficult than for finite strings. Not the computation part but the complexity assignment part.

eigenket 3y ago
I agree there is a bunch of complexity in generalising Kolmogorov complexity to general infinite strings. However I'm not really trying to do that here, all I want is enough to back-up the statement I made before, that the complexity of pi is finite. Doing that is much more trivial than what you're talking about. Theres a bunch of fine detail in getting it down to defining an actual number measuring complexity which I don't care about at all, all I care about (in the context of this discussion) is that the number is finite.