Talk:Algorithmic information theory

The following remarks pertain to the article Algorithmic Information Theory. The article as it stands has some issues that I would like to bring to discussion. I hope that some consensus can be reached about how to deal with them.

There are no references.
Komogorov complexity is an active research area in mathematics as well as computer science.
The statement

Unlike classical information theory, algorithmic information theory gives formal,
rigorous definitions of a random string.....

is a point of view that is not universally shared, although it has been championed by Chaitin in popularizations of the area. It is well known that the AIT definition of random string is actually only asymptotically well defined, so the viewpoint that AIT does not give a formal definition of a random string is equally valid (and, among mathematicians I have spoken with, a common viewpoint). The issue is the lack of a canonical choice of a universal machine.

The definition of random infinite sequence has the same extent as the one given by Martin Lof, and this should be mentioned.

CMummert 04:37, 16 June 2006 (UTC)[reply]

This is a stub. If you want to add more content or more references, feel free. However, it is a fact that classical information theory gives no definition of a random string or random infinite sequence (nor does it make any attempt, focusing as it does on random processes), whereas AIT does. Maybe there are those who don't like the definitions for aesthetic reasons, but they exist nonetheless, and have numerous applications in theoretical computer science, e.g.

the result of Allender et al (Power from Random Strings) that PSPACE ⊆ P^R, where R is the set of Kolmogorov random strings
the incompressibility method to prove lower bounds such as the average case complexity of Heapsort as described in Li and Vitanyi (An Introduction to Kolmogorov Complexity and its Applicaions)
many, many others

The definition of a random string is formal, so long as one accepts that Turing machines are formal mathematical objects, and it is rigorous and robust, as the above mentioned results, and many others, do not depend on the choice of universal machine. If you are aware of results in pure mathematics that demonstrate that the definition of a random string or sequence is frail, please add these results. The notion that these definitions are robust to the choice of universal machine predates Chaitin. This robustness is due to the invariance theorem (Lemma 2.1.1 in Li and Vitanyi), first proven by Solomonoff in 1964. Finally, I'm afraid I don't understand your final point:

The definition of random infinite sequence has the same extent as the one given by Martin Lof, and this should be mentioned.

Is there another definition you are thinking of? (e.g. Schnorr randomness?) Pexatus 22:16, 17 June 2006 (UTC)[reply]

Yes the definition of a Komogorv random string is rigorous, but only once you have fixed some universal Turing machine (or universal prefix-free machine). There is no definition which in any canonical manner declares that particular finite strings are random while others aren't. By uncanonical I mean that any fixed string is random with respect to some universal machines and nonrandom with respect to other machines (by Kraft's theorem, any string can be given any Kolmogorov complexity). For particular results that use the existence of random strings, such as the incompressibility method, the lack of canonicity is not important. But it is important that the article doesn't claim that there is a way to canonically say that particular strings are random and others are not. That is, the theory does not lead to an unambiguous answer to the question Is the string 10101010111 random?'

So the quote

Unlike classical information theory, algorithmic information theory gives formal,
rigorous definitions of a random string.....

Should say

Unlike classical information theory, algorithmic information theory gives a formal,
rigorous definition of a random string, although this definition requires a noncanonical 
choice of a universal Turing machine.

or something like that. I would like to come to a consensus on the talk page about the best way to phrase it before editing the article.

Kolmogorov complexity does give a canonical definition of a random infinite sequence, because any two universal machines give the same asymptotic complexities up to a constant. This definition of random infinite sequence gives exactly the same collection of random infinite sequences as the definition of a random infinite sequence due to Martin Löf, which says that a infinite sequence is random if it does not lie in any effective measure 0 set. The fact that these two definitions agree is usually presented as part of the motivation for these definitions. CMummert 02:14, 18 June 2006 (UTC)[reply]