Abstract:
We show that the classical Hausdorff and constructive dimensions of
any union of Π^{0}_{1} -definable sets of binary
sequences are equal. If the union is effective, that is, the set of
sequences is Σ^{0}_{2}-definable, then the
computable dimension also equals the Hausdorff dimension. This second
result is implicit in the work of Staiger (1998). Staiger also proved
related results using entropy rates of decidable languages. We show
that Staiger's computable entropy rate provides an equivalent
definition of computable dimension. We also prove that a constructive
version of Staiger's entropy rate coincides with constructive
dimension.
Journal Version: