Editing Chaitin's constant (section)

== Uncomputability ==
A real number is called computable if there is an algorithm which, given {{mvar|n}}, returns the first {{mvar|n}} digits of the number. This is equivalent to the existence of a program that enumerates the digits of the real number.

No halting probability is computable. The proof of this fact relies on an algorithm which, given the first {{mvar|n}} digits of {{math|&Omega;}}, solves Turing's [[halting problem]] for programs of length up to {{mvar|n}}. Since the halting problem is [[Undecidable problem|undecidable]], {{math|&Omega;}} cannot be computed.

The algorithm proceeds as follows.  Given the first {{mvar|n}} digits of {{math|&Omega;}} and a {{math|''k'' ≤ ''n''}}, the algorithm enumerates the domain of {{mvar|F}} until enough elements of the domain have been found so that the probability they represent is within {{math|2{{sup|−(''k''+1)}}}} of {{math|&Omega;}}. After this point, no additional program of length {{mvar|k}} can be in the domain, because each of these would add {{math|2{{sup|−''k''}}}} to the measure, which is impossible. Thus the set of strings of length {{mvar|k}} in the domain is exactly the set of such strings already enumerated.