Trivial Reals

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

Status: published in R. Downey, D. Decheng, T. S. Ping, Q. Y. Hui, and M. Yasugi, eds., Proceedings of the 7th and 8th Asian Logic Conferences, Singapore University Press and World Scientific, Singapore, 2003, 103 - 131.

Availability: published version and preprint

Abstract. Solovay showed that there are noncomputable reals α such that H(α | 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.