Relativizing Chaitin's Halting Probability

by Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies



Status: published in the Journal of Mathematical Logic, vol. 5 (2005), pp. 167 - 192.

Availability: PostScript, DVI, and PDF

Abstract. As a natural example of a 1-random real, Chaitin proposed the halting probability Omega of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U. Let OmegaAU be the halting probability of UA; this gives a natural uniform way of producing an A-random real for every real A. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability theory and this Omega operator. But unlike the jump, which is invariant (up to computable permutation) under the choice of an effective enumeration of the partial computable functions, OmegaAU can be vastly different for different choices of U. Even for a fixed U, there are oracles A =* B such that OmegaAU and OmegaBU are 1-random relative to each other. We prove this and many other interesting properties of Omega operators. We investigate these operators from the perspective of analysis, computability theory, and of course, algorithmic randomness.


drh@math.uchicago.edu