4 ms·
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 direc
by 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 agoI 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.