Fernando Martinez, Juntao Chen, et al.
AAAI 2025
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.
Fernando Martinez, Juntao Chen, et al.
AAAI 2025
I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences