Another Example of Higher Order Randomness

Article type: Research Article

Authors: Becher, Verónica | Chaitin, Gregory

Affiliations: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, (1428) Buenos Aires, Argentina | IBM Thomas J. Watson Research Center, P O Box 218, Yorktown Heights, NY 10598, USA

Abstract: We consider the notion of algorithmic randomness relative to an oracle. We prove that the probability β that a program for infinite computations (a program that never halts) outputs a cofinite set is random in the second jump of the halting problem. Indeed, we prove that β is exactly as random as the halting probability of a universal machine equipped with an oracle for the second jump of the halting problem, in spite of the fact that β is defined without considering oracles.

Keywords: randomness, program size complexity, infinite computations

Journal: Fundamenta Informaticae, vol. 51, no. 4, pp. 325-338, 2002