Chaitin's Constant - Properties

Properties

Each Chaitin constant Ω has the following properties:

• It is algorithmically random. This means that the shortest program to output the first n bits of Ω must be of size at least n-O(1). This is because, as in the Goldbach example, those n bits enable us to find out exactly which programs halt among all those of length at most n.
• It is a normal number, which means that its digits are equidistributed as if they were generated by tossing a fair coin.
• It is not a computable number; there is no computable function that enumerates its binary expansion, as discussed below.
• The set of rational numbers q such that q < Ω is computably enumerable; a real number with such a property is called a left-c.e. real number in recursion theory.
• The set of rational numbers q such that q > Ω is not computably enumerable.
• Ω is an arithmetical number.
• It is Turing equivalent to the halting problem and thus at level of the arithmetical hierarchy.

Not every set that is Turing equivalent to the halting problem is a halting probability. A finer equivalence relation, Solovay equivalence, can be used to characterize the halting probabilities among the left-c.e. reals.