Abstract:
We consider the notion of randomness relative to an oracle: a real number is
random in A if and only if its initial segments are algorithmically incompressible
in a self-delimiting universal machine equipped with an oracle A. We prove that
the probability that a program for infinite computations outputs a cofinite set is
random in the second jump of the halting problem.