INVESTIGADORES
BECHER veronica Andrea
artículos
Título:
Another example of higher order randomness
Autor/es:
VERÓNICA BECHER; GREGORY CHAITIN
Revista:
FUNDAMENTA INFORMATICAE
Editorial:
IOS PRESS
Referencias:
Año: 2002 vol. 51 p. 325 - 338
ISSN:
0169-2968
Resumen:
Abstract. We consider the notion of algorithmic randomness relative to an oracle. We prove thatthe 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.
