×

Lowness for effective Hausdorff dimension. (English) Zbl 1335.03040

Summary: We examine the sequences A that are low for dimension, i.e. those for which the effective (Hausdorff) dimension relative to \(A\) is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Löf random sequence has effective dimension 1 relative to \(A\), and lowishness for \(K\), namely, that the limit of \(K^{A}(n)/K(n)\) is 1. We show that there is a perfect \(\Pi_1^0\)-class of low for dimension sequences. Since there are only countably many low for random sequences, many more sequences are low for dimension. Finally, we prove that every low for dimension is jump-traceable in order \(n^{\epsilon}\), for any \(\epsilon >0\).

MSC:

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

References:

[1] DOI: 10.1007/s11856-012-0012-5 · Zbl 1279.03065 · doi:10.1007/s11856-012-0012-5
[2] DOI: 10.1016/0304-3975(76)90005-0 · Zbl 0328.02029 · doi:10.1016/0304-3975(76)90005-0
[3] DOI: 10.1147/rd.214.0350 · Zbl 0362.94035 · doi:10.1147/rd.214.0350
[4] DOI: 10.1007/s11856-011-0217-z · Zbl 1273.03141 · doi:10.1007/s11856-011-0217-z
[5] Downey R. G., Theory and Applications of Computability (2010)
[6] DOI: 10.1016/S0019-9958(86)80004-3 · Zbl 0628.03024 · doi:10.1016/S0019-9958(86)80004-3
[7] DOI: 10.2178/jsl.7804130 · Zbl 1350.03033 · doi:10.2178/jsl.7804130
[8] Hirschfeldt D. R., Computability 1 pp 85– (2012)
[9] DOI: 10.1090/S0002-9939-07-08648-0 · Zbl 1128.03031 · doi:10.1090/S0002-9939-07-08648-0
[10] DOI: 10.1112/jlms/jdr072 · Zbl 1262.03068 · doi:10.1112/jlms/jdr072
[11] DOI: 10.1007/BFb0076224 · doi:10.1007/BFb0076224
[12] Levin L. A., Problemy Peredači Informacii 10 pp 30– (1974)
[13] DOI: 10.1007/3-540-45022-X_76 · doi:10.1007/3-540-45022-X_76
[14] DOI: 10.1016/S0020-0190(02)00343-5 · Zbl 1045.68570 · doi:10.1016/S0020-0190(02)00343-5
[15] DOI: 10.1016/j.aim.2004.10.006 · Zbl 1141.03017 · doi:10.1016/j.aim.2004.10.006
[16] DOI: 10.1093/acprof:oso/9780199230761.001.0001 · Zbl 1237.03027 · doi:10.1093/acprof:oso/9780199230761.001.0001
[17] Ryabko B. Ya., Dokl. Akad. Nauk SSSR 277 pp 1066– (1984)
[18] DOI: 10.1002/malq.200710012 · Zbl 1123.03040 · doi:10.1002/malq.200710012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.