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:
- 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.