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(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.
drh@math.uchicago.edu