##
Trivial Reals

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*(1^{n})+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.

drh@math.uchicago.edu