Page "Chaitin's constant" Paragraph 39

As mentioned above, the first n bits of Gregory Chaitin's constant Omega are random or incompressible in the sense that we cannot compute them by a halting algorithm with fewer than n-O ( 1 ) bits.

However, consider the short but never halting algorithm which systematically lists and runs all possible programs ; whenever one of them halts its probability gets added to the output ( initialized by zero ).

After finite time the first n bits of the output will never change any more ( it does not matter that this time itself is not computable by a halting program ).

So there is a short non-halting algorithm whose output converges ( after finite time ) onto the first n bits of Omega.

In other words, the enumerable first n bits of Omega are highly compressible in the sense that they are limit-computable by a very short algorithm ; they are not random with respect to the set of enumerating algorithms.

Jürgen Schmidhuber ( 2000 ) constructed a limit-computable " Super Omega " which in a sense is much more random than the original limit-computable Omega, as one cannot significantly compress the Super Omega by any enumerating non-halting algorithm.