TY - JOUR

T1 - Lowness for Effective Hausdorff Dimension

AU - Turetsky, Daniel

AU - Lempp, Steffen

AU - Miller, Joe

AU - Weber, Rebecca

AU - Ng, Keng Meng

N1 - Publisher Copyright:
© 2014 World Scientific Publishing Company.

PY - 2014

Y1 - 2014

N2 - 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 KA(n)/K(n) is 1.We show that there is a perfect Π01-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ε, for any ε > 0.

AB - 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 KA(n)/K(n) is 1.We show that there is a perfect Π01-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ε, for any ε > 0.

KW - effective Hausdorff dimension

KW - Kolmogorov complexity

KW - lowness

KW - Martin-Löf randomness

UR - http://www.scopus.com/inward/record.url?scp=84929164774&partnerID=8YFLogxK

U2 - 10.1142/S0219061314500111

DO - 10.1142/S0219061314500111

M3 - Article

VL - 14

JO - Journal of Mathematical Logic

JF - Journal of Mathematical Logic

SN - 0219-0613

IS - 2

M1 - 1450011

ER -