Editing Chaitin's constant (section)

== Properties ==
Each Chaitin constant {{math|&Omega;}} has the following properties:

* It is [[algorithmic randomness|algorithmically random]] (also known as Martin-Löf random or 1-random).{{sfn|Downey|Hirschfeldt|2010|loc=Theorem 6.1.3}} This means that the shortest program to output the first {{mvar|n}} bits of {{math|&Omega;}} must be of size at least {{math|''n'' − O(1)}}. This is because, as in the Goldbach example, those {{mvar|n}} bits enable us to find out exactly which programs halt among all those of length at most {{mvar|n}}.
* As a consequence, 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 number]]s {{mvar|q}} such that {{math|''q'' < &Omega;}} is [[computably enumerable set|computably enumerable]];{{sfn|Downey|Hirschfeldt|2010|loc=Theorem 5.1.11}} a real number with such a property is called a left-c.e. real number in [[recursion theory]].
* The set of rational numbers {{mvar|q}} such that {{math|''q'' > &Omega;}} is not computably enumerable. (Reason: every left-c.e. real with this property is computable, which {{math|&Omega;}} is not.)
* It is an [[arithmetical number]].
* It is [[Turing degree|Turing equivalent]] to the [[halting problem]] and thus at level {{math|{{SubSup|{{noitalic|&Delta;}}|2|0}}}} of the [[arithmetical hierarchy]].

Not every set that is Turing equivalent to the halting problem is a halting probability. A [[equivalence relation#Comparing equivalence relations|finer]] equivalence relation, Solovay equivalence, can be used to characterize the halting probabilities among the left-c.e. reals.{{sfn|Downey|Hirschfeldt|2010|p=405}} One can show that a real number in {{math|[0,1]}} is a Chaitin constant (i.e. the halting probability of some prefix-free universal computable function) if and only if it is left-c.e. and algorithmically random.{{sfn|Downey|Hirschfeldt|2010|p=405}} {{math|&Omega;}} is among the few [[Definable real number|definable]] algorithmically random numbers and is the best-known algorithmically random number, but it is not at all typical of all algorithmically random numbers.{{sfn|Downey|Hirschfeldt|2010|pp=228–229}}