Trivial Reals

by Rod Downey, Denis R. Hirschfeldt, André Nies, and Frank Stephan

Status: published in the Proceedings of the 7th and 8th Asian Logic Conferences (R. Downey, D. Decheng, T. S. Ping, Q. Y. Hui, and M. Yasugi, eds.), Singapore University Press and World Scientific, Singapore, 2003, pp. 103 - 131 (extended abstract in Electronic Notes in Theoretical Computer Science vol. 66, no. 1).

Availability: DVI, PDF, and PostScript

Abstract. Solovay showed that there are noncomputable reals alpha such that H(alpha | n) < H(1n)+O(1), where H is prefix-free Kolmogorov complexity. Such H-trivial reals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an H-trivial real. We also analyze various computability-theoretic properties of the H-trivial reals, showing for example that no H-trivial real can compute the halting problem (which means that our construction of an H-trivial computably enumerable set is a particularly easy, injury-free construction of an incomplete c.e. set). Finally, we relate the H-trivials to other classes of "highly nonrandom" reals that have been previously studied.