Chaitin $\Omega$ Numbers, Solovay Machines, and Incompleteness

Abstract

Computably enumerable (c.e.) reals can be coded by Chaitin machines through their halting probabilities. Tuning Solovay's construction of a Chaitin universal machine for which ZFC (if arithmetically sound) cannot determine any single bit of the binary expansion of its halting probability, we show that every c.e. random real is the halting probability of a universal Chaitin machine for which ZFC cannot determine more than its initial block of 1 bits – as soon as you get a 0 it's all over. Finally, a constructive version of Chaitin information-theoretic incompleteness theorem is proven.