##
Trivial Reals

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*(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