ECCC-Report TR16-139https://eccc.weizmann.ac.il/report/2016/139Comments and Revisions published for TR16-139en-usFri, 02 Jun 2017 15:03:00 +0300
Revision 1
| Exact constructive and computable dimensions |
Ludwig Staiger
https://eccc.weizmann.ac.il/report/2016/139#revision1In this paper we derive several results which generalise the constructive
dimension of (sets of) infinite strings to the case of exact dimension. We
start with proving a martingale characterisation of exact Hausdorff
dimension. Then using semi-computable super-martingales we introduce the
notion of exact constructive dimension of (sets of) infinite strings. This
allows us to derive several bounds on the complexity functions of infinite
strings, that is, functions assigning to every finite prefix its Kolmogorov
complexity. In particular, it is shown that the exact Hausdorff dimension
of a set of infinite strings lower bounds the maximum complexity function
of strings in this set. Furthermore, we show a result bounding the exact
Hausdorff dimension of a set of strings having a certain computable
complexity function as upper bound.
Obviously, the Hausdorff dimension of a set of strings alone without any
computability constraints cannot yield upper bounds on the complexity of
strings in the set. If we require, however, the set of strings to be
$\Sigma_{2}$-definable several results upper bounding the complexity by the
exact Hausdorff dimension hold true. First we prove that for a
$\Sigma_{2}$-definable set with computable dimension function one can
construct a computable -- not only semi-computable -- martingale succeeding
on this set. Then, using this result, a tight upper bound on the prefix
complexity function for all strings in the set is obtained.Fri, 02 Jun 2017 15:03:00 +0300https://eccc.weizmann.ac.il/report/2016/139#revision1
Paper TR16-139
| Exact constructive and computable dimensions |
Ludwig Staiger
https://eccc.weizmann.ac.il/report/2016/139In this paper we derive several results which generalise the constructive
dimension of (sets of) infinite strings to the case of exact dimension. We
start with proving a martingale characterisation of exact Hausdorff
dimension. Then using semi-computable super-martingales we introduce the
notion of exact constructive dimension of (sets of) infinite strings. This
allows us to derive several bounds on the complexity functions of infinite
strings, that is, functions assigning to every finite prefix its Kolmogorov
complexity. In particular, it is shown that the exact Hausdorff dimension
of a set of infinite strings lower bounds the maximum complexity function
of strings in this set. Furthermore, we show a result bounding the exact
Hausdorff dimension of a set of strings having a certain computable
complexity function as upper bound.
Obviously, the Hausdorff dimension of a set of strings alone without any
computability constraints cannot yield upper bounds on the complexity of
strings in the set. If we require, however, the set of strings to be
$\Sigma_{2}$-definable several results upper bounding the complexity by the
exact Hausdorff dimension hold true. First we prove that for a
$\Sigma_{2}$-definable set with computable dimension function one can
construct a computable -- not only semi-computable -- martingale succeeding
on this set. Then, using this result, a tight upper bound on the prefix
complexity function for all strings in the set is obtained.Sat, 10 Sep 2016 04:02:19 +0300https://eccc.weizmann.ac.il/report/2016/139