I am of course familiar with all that – that's just why I said 'choose any correct algorithm' rather than 'choose the correct algorithm'. The example of getting all heads from random coin flips (or anything similar) shows a difficulty in defining 'random' data – as you would, I am sure, admit, we can't prove that some given data can't be produced by an algorithm shorter than itself – all we can do is show its statistical indistinguishability from the output of a truly random process. ]]>

…and what most people think would be a random distribution of points in a 2-D space is closer to a uniform distribution. A true random distribution shows clusters. This has led to big arguments about clustering of diseases near nuclear or chemical plants. ]]>

And Las Vegas makes a lot of money on the confusion… ]]>

But that's not what the article is saying. It's describing what Kolomogorov complexity means, and giving examples. "Print a thousand 9s" is an example of instructions that give a 1000-digit string composed entirely of 9s, but it may or may not be the *shortest possible* instructions that give that same string.

The same thing is going on in "print the first thousand digits of π using the following formula…". This is supposed to be an example of instructions from which Kolmogorov complexity will be measured. Valid instructions provide an upper bound on the Kolmogorov complexity of the string.

To be valid instructions, you have to specify the formula you're using. "Print the first thousand digits of pi" is illegitimate – how are you supposed to follow those instructions? There is a problem in this example, but it isn't the words "using the following formula"; it's the meaningless words that precede them, "print the first thousand digits of pi".

Philip Taylor is thinking of the *question* "what is the Kolmogorov complexity of the first 1000 digits of pi?", but the article is thinking of the *answer* "at most this much, because I can use this formula to produce those digits".

The one-time pad in fact uses a symmetric function, as far from one-way as possible, and yet is easily seen perfectly secure (and the converse is also proven – no other cipher can resist infinite computational power); its security lies wholly in the key.

Philip Taylor is surely right that, for complexity determination, the shortest program must be free to choose any correct algorithm, or the definition would be arbitrary (it is already arbitrary what 'machine' it is run on, but as long as it is Turing-complete and the same for the problems being compared, comparison is legitimate).

k_over_hbarc at yahoo.com

]]>the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output.

Now if we want to compute the Kolmogorov complexity of the first 1000 digits of pi, surely "the shortest computer program" must be able to use any formula, not just one particular one, must it not ?

]]>But/and "formula" is really an instance of "description"… and not every description is given by a (straightforward) plug-and-chug formula. That is, a description can involve branching logic, as in "if the last digit was X, then compute the following digit one way, and if the last digit was _not_ X, compute it this other way". Or, generally, computer programs, with their potential logical complexity…

But, interestingly, sometimes a tricky branching (recursive!?!) program can be much shorter than a more "linear" logical/formulaic presentation of an object. In that case, the object still does have a low complexity. The catch is that it is provably essentially impossible to effectively compute the complexity of objects (see Goedel, Turing, Kolmogorov, Solomonoff, Chaitin, et al), that is, it is impossible determine whether there is some tricky much-shorter "program" which will describe/produce the object at hand.

My own impression is that to truly understand complexity is akin to understanding P versus NP and such stuff. I'll be amazed if/when people make genuine progress.

]]>