Finite Self-Information
Status: published in Computability 1
(2012) 85 - 98.
Availability: journal
version and preprint
Abstract. We present a definition, due to Levin, of mutual
information I(A:B) for infinite sequences. We
say that a set A has finite self-information if
I(A:A) < ∞. It is easy to see that every K-trivial
set has finite self-information. We answer a question of Levin by showing
that the converse does not hold. Finally, we investigate the
connections between having finite self-information and other notions of
weakness such as jump-traceability. In particular, we show that our
proof can be adapted to produce a set that is low for both effective
Hausdorff dimension and effective packing dimension, but
not K-trivial.
drh@math.uchicago.edu