1
$\begingroup$

I am reading this article: http://plus.maths.org/content/os/issue37/features/omega/index, and I came across the following, a topic from probability:

Suppose there are two programs in the whole world that halt, and their binary representations are $11001$ and $101$. We know from probability theory that if the experiment is:

  1. Flip $N$ fair coins.

Then, the probability of getting any sequence is: $\left(\frac{1}{2}\right)^N$. So the probability of generating $11001$ is $\left(\frac{1}{2}\right)^5$ and the probability of generating $101$ is $\left(\frac{1}{2}\right)^3$.

Now, a line from the article reads:

The probability of randomly choosing one of these programs is $1/2^3 + 1/2^5 = 0.15625$.

How is this calculated? What is the experiment? The formula for union of two events is: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$. I am asking this because it is possible for the probability calculation in the article to exceed $1$. For example, suppose if any 3-bit sequence halted, then the probability would be $8*1/2^3 + 1/2^5 = 1.03125$. This would violate one of the axioms of probability.

Thanks.

1 Answers 1

1

Chaitin assumes that the programs are self-delimiting, meaning that the programs indicate their size as well as their content.

For example, suppose you had a program of length five, represented as 11001. Then because the programs are assumed to be self-delimiting, 110 cannot also be a program, since it is the first three bits of 11001. So you can't have eight programs of length three and one program of length five.

Self-delimiting programs are prefix-codes. Look up the Kraft inequality.

  • 0
    Chaitin's website is the best source of information on this. I think his book Meta-Math is his best work. You can find it on arxiv.2012-11-19