Extracting information is hard: A Turing degree of non-integral effective Hausdorff dimension
By Joseph S. Miller. 2011
49 citations recorded by the source corpus.
Abstract We construct a Δ 2 0 infinite binary sequence with effective Hausdorff dimension 1/2 that does not compute a sequence of higher dimension. Introduced by Lutz, effective Hausdorff dimension can be viewed as a measure of the information density of a sequence. In particular, the dimension of A ∈ 2 ω is the lim inf of the ratio between the information content and length of initial segments of A . Thus the main result demonstrates that it is not always possible to extract information from a partially random source to produce a sequence that has higher information density.
Subfields: Computational Theory and Mathematics, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/4af88046e544d20fe1eb79c87979420f4cb53db1
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Mathematical Physics
Citations in the corpus
- Medvedev degrees of two-dimensional subshifts of finite type (2012, background): “Among these topics are reverse mathematics [36, 39], almost everywhere domination [42], measure-theoretic regularity [44], the hyperarithmetical hierarchy [12, 44], effective Hausdorff dimension [24, 46] and Kolmogorov complexity [20].”