Chaitin's Constant - Interpretation As A Probability

Interpretation As A Probability

The Cantor space is the collection of all infinite sequences of 0s and 1s. A halting probability can be interpreted as the measure of a certain subset of Cantor space under the usual probability measure on Cantor space. It is from this interpretation that halting probabilities take their name.

The probability measure on Cantor space, sometimes called the fair-coin measure, is defined so that for any binary string x the set of sequences that begin with x has measure 2-|x|. This implies that for each natural number n, the set of sequences f in Cantor space such that f(n) = 1 has measure 1/2, and the set of sequences whose nth element is 0 also has measure 1/2.

Let F be a prefix-free universal computable function. The domain P of F consists of an infinite set of binary strings

.

Each of these strings p_i determines a subset S_i of Cantor space; the set S_i contains all sequences in cantor space that begin with p_i. These sets are disjoint because P is a prefix-free set. The sum

represents the measure of the set

.

In this way, Ω_F represents the probability that a randomly selected infinite sequence of 0s and 1s begins with a bit string (of some finite length) that is in the domain of F. It is for this reason that Ω_F is called a halting probability.