Abstract:
A Chaitin Omega number is the halting probability of a universal prefix-free
Turing machine. Every Omega number is simultaneously computably enumerable
(the limit of a computable, increasing, converging sequence of rationals), and algorithmically
random (its binary expansion is an algorithmic random sequence), hence
uncomputable. The value of an Omega number is highly machine-dependent. In
general, no more than finitely many scattered bits of the binary expansion of an
Omega number can be exactly computed; but, in some cases, it is possible to prove
that no bit can be computed.
In this paper we will simplify and improve both the method and its correctness
proof proposed in an earlier paper, and we will compute the exact approximations
of two Omega numbers of the same prefix-free Turing machine, which is universal
when used with data in base 16 or base 2: we compute 43 exact bits for the base 16
machine and 40 exact bits for the base 2 machine.