##
Relativizing Chaitin's Halting Probability

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

Availability: journal
version and preprint

**Abstract.** As a natural example of a 1-random real, Chaitin
proposed the halting probability Ω of a universal
prefix-free machine. We can relativize this example by considering a
universal prefix-free oracle machine *U*. Let
Ω^{A}_{U} be the halting
probability of *U*^{A}; 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,
Ω^{A}_{U} can be vastly
different for different choices of *U*. Even for a fixed
*U*, there are oracles *A* =^{*} *B* such that
Ω^{A}_{U} and
Ω^{B}_{U} 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