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).
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.