Finite Self-Information

by Denis R. Hirschfeldt and Rebecca Weber



Status: Computability 1 (2012) 85 - 98.

Availability: PDF

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