Sixty-four bits of Ω

Fix a universal prefix-free machine $U$ and feed it fair coin flips. Chaitin’s constant is the probability that it halts:

Prefix-freeness makes the sum legal — Kraft’s inequality caps it at 1 — and makes the number strange. The first $n$ bits of $\Omega_U$ decide the halting problem for every program of length at most $n$: dovetail all computations, accumulate $2^{-|p|}$ for each halt, and once the running total passes the $n$-bit truncation, any short program still running never halts, since its contribution alone would overshoot. A finite prefix of one real number settles infinitely many instances of the unsolvable.

The price is that the bits themselves are lawless. $\Omega_U$ is Martin-Löf random — its bit sequence passes every effective statistical test — and any consistent, computably axiomatized theory can determine at most finitely many of its bits (Chaitin’s incompleteness; Solovay sharpened it to machines for which ZFC pins down not a single one).1

And yet: for one concrete machine, Calude, Dinneen, and Shu computed the first 64 bits exactly, by settling the halting behavior of every sufficiently short program by hand and by argument. In decimal,

No contradiction — the theorem forbids keeping up with $\Omega$, not starting. The wall stands; they measured its first four digits, $0{.}0078$, and this article shelves the number accordingly.2