R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering
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.
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering
Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
Imran Nasim, Melanie Weber
SCML 2024
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems