Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
Hi Craig Feinstein, thank you for your answer. I thought it had something to do with coding theory since the summation expression shows up there as well. Fortunately, I have the Elements of Information Theory book in front of me and I will definitely be reading through those chapters. –  jrand Nov 19 '12 at 18:09
    
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. –  Craig Feinstein Nov 19 '12 at 19:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.