A perfect set of reals with finite self-information. (English) Zbl 1350.03033

Summary: We examine a definition of the mutual information of two reals proposed by L. A. Levin [Probl. Peredachi Inf. 10, No. 3, 30–35 (1974; Zbl 0312.94007)]. The mutual information is
\[ I(A:B)=\log\sum\limits_{\sigma,\tau\in 2^{<\omega}} 2^{K(\sigma)-K^A(\sigma)+K(\tau)-K^B(\tau)-K(\sigma,\tau)}, \] where \(K(\cdot)\) is the prefix-free Kolmogorov complexity. A real \(A\) is said to have finite self-information if \(I(A:A)\) is finite. We give a construction for a perfect \(\Pi^0_1\) class of reals with this property, which settles some open questions posed by D. R. Hirschfeldt and R. Weber [Computability 1, No. 1, 85–98 (2012; Zbl 1283.68174)]. The construction produces a perfect set of reals with \(K(\sigma)\leq^+ K^{A}(\sigma)+f(\sigma)\) for any given \(\Delta^0_2\) \(f\) with a particularly nice approximation and for a specific choice of \(f\) it can also be used to produce a perfect \(\Pi^0_1\) set of reals that are low for effective Hausdorff dimension and effective packing dimension. The construction can be further adapted to produce a single perfect set of reals that satisfy \(K(\sigma) \leq^+ K^A(\sigma)+f(\sigma)\) for all \(f\) in a ‘nice’ class of \(\Delta^0_2\) functions which includes all \(\Delta^0_2\) orders.


03D32 Algorithmic randomness and dimension
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI arXiv Euclid