You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Finite Self-Information

Article type: Research Article

Authors: Hirschfeldt, Denis R. | Weber, Rebecca;

Affiliations: Department of Mathematics, University of Chicago, USA | Department of Mathematics, Dartmouth College, USA

Note: [] E-mail: [email protected]

Note: [] E-mail: [email protected]

Note: [] Both authors were partially supported by a National Science Foundation Focused Research Group grant, DMS-0652521 and DMS-0653226. Hirschfeldt was also supported by NSF grants DMS-0801033 and DMS-1101458. Both authors also acknowledge the support of the American Institute of Mathematics, as the question answered in this paper was formulated during a meeting they attended at the AIM Research Conference Center.

Keywords: mutual information, K-triviality, Kolmogorov complexity, effective dimension, jump traceability

DOI: 10.3233/COM-2012-003

Journal: Computability, vol. 1, no. 1, pp. 85-98, 2012

Published: 2012
Get 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.

Show less