Talk:Algorithmic information theory

From Wikipedia, the free encyclopedia

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)

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)

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)

The way this is usually phrased in my research community (theoretical computer science) is that the Kolmogorov complexity of a string is well-defined up to a constant depending on the choice of universal machine. Maybe the sentence could be

Unlike classical information theory, algorithmic information theory gives a formal, 
rigorous definition of a random string. The set of random strings depends on the choice
of the universal Turing machine used to define Kolmogorov complexity, but any choice
gives identical asymptotic results, since the Kolmogorov complexity of a string is
invariant up to an additive constant depending only on the choice of universal Turing 
machine.

All the results I know of are asymptotic, even when dealing with finite strings, since we are making claims about infinite sets of strings, OR they are statements about individual strings that begin with "There is a constant c such that...". For instance, in the example above from Allender et al, the set of random strings changes with the universal machine, but any of these sets has sufficient power to decide all of PSPACE in polynomial time. Therefore, even though there are an infinite number of ways to define the set of Kolmogorov random strings, every one of these definitions results in the exact same theory of algorithmic information, including finite string results. And there are those who believe that there is in fact a canonical universal machine, the one which requires the fewest bits to encode, and that this number is a fundamental constant of the universe every bit as important as the charge on an electron or Avogadro's Number.

The multiple equivalent definitions of random infinite sequences are discussed on the page for algorithmically random sequences. If you are going to edit this article, make sure you look at algorithmically random sequence and Kolmogorov complexity to make sure not to introduce too much overlap between the articles. Pexatus 02:52, 18 June 2006 (UTC)

[edit] A second quibble

The sentence that says Omega is

a real number which expresses the probability that 
a random computer program will eventually halt. 

is not literally correct. There is no nontrivial measure on the set of programs, and thus there is no formal sense to the phrase 'random computer program'. What is true is that Omega gives the probability that a random infinite binary sequence has some initial string that is the index of a program that halts.

To see what is wrong with the phrase `random computer program' consider the supposed experiment in which a coin is flipped until the index of a valid program has been obtained, at which point the flipping stops. What if no such program is ever obtained? It can be shown that this is possible for any prefix free universal machine. Thus the coin flipping procedure is not a valid probability experiment. If you were to compute the conditional probability only relative to those infinite sequences that begin with the index of a program then the conditional probability you get would not, in general, be equal to Omega. It would be Omega divided by the measure of the set of infinite sequences that start with the index of a program. CMummert 02:20, 18 June 2006 (UTC)

The stuff about Chaitin seems to be hastily written. I'm sure this could be cleaned up (and references to other researchers besides Chaitin added). A better way to phrase that would be

Omega is a real number which expresses the probability that a self-delimiting
universal Turing machine will halt when its input is supplied by flips
of a fair coin.

The event space is the set of all infinite sequences that could be pre-placed on the input tape, and the event "U halts while reading the input tape supplied" is the event with probability Omega.

[edit] OK?

Here are slightly edited version extending Pexatus's proposed sentences. Are they OK with everyone?

Unlike classical information theory, algorithmic information theory gives a formal, 
rigorous definition of a random string. (The set of random strings depends on the choice
of the universal Turing machine used to define Kolmogorov complexity, but any choice
gives identical asymptotic results because the Kolmogorov complexity of a string is
invariant up to an additive constant depending only on the choice of universal Turing  
machine.)

Ω is a real number which expresses the probability that a self-delimiting
universal Turing machine will halt when its input is supplied by flips
of a fair coin.  Athough Ω is easily defined, it is impossible to determine 
infinitely many of its binary digits in any consistent axiom system; this 
result is similar to Gödel's Incompleteness Theorem in establishing the
unprovability of certain statements in formal theories.  Although the digits of Ω 
cannot be determined, many properties of Ω are known; for example, it is an 
algorithmically random sequence and thus its binary digits are equidistributed.
From the point of view of computability theory, Omega is of the same Turing degree
as the halting problem.

Pexatus: thanks for pointing out algorithmically random sequence. I would never have found it with that name. They are called 1-random reals in computability theory. CMummert 12:05, 20 June 2006 (UTC)

Looks good. I personally think that it is easier to see that Ω is uncomputable because access to it allows one to solve the halting problem, but since I'm not a logic guy, I guess I have a different notion of what is easy to see. I would remove the part about its digits being equidistributed (i.e., it is simply normal), as that might give the false impression that that is the definition of a random sequence. At some point, self-delimiting Turing machine should be given its own entry and linked from here. (a Turing machine with a read-only input tape whose read head may only move to the right, and which is defined such that its computation is invalid if the read head is not on the final character of the input sequence when the machine halts). Pexatus 18:35, 20 June 2006 (UTC)

Thanks for the feedback. I'll cut the equidistributed part (the whole clause starting with and thus). The Turing degree is the easiest way for me to see that Omega is uncomputable, as well, although I don't know any really easy proof. CMummert 22:49, 20 June 2006 (UTC)