ECCC-Report TR16-013https://eccc.weizmann.ac.il/report/2016/013Comments and Revisions published for TR16-013en-usWed, 07 Oct 2020 15:24:44 +0300
Revision 2
| Bounds on the Kolmogorov complexity function for infinite words |
Ludwig Staiger
https://eccc.weizmann.ac.il/report/2016/013#revision2The Kolmogorov complexity function of an infinite word $\xi$ maps a natural
number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We
investigate the maximally achievable complexity function if $\xi$ is taken
from a constructively describable set of infinite words. Here we are
interested in linear upper bounds where the slope is the Hausdorff
dimension of the set.
As sets we consider $\Pi_{1}$-definable sets obtained by dilution and sets
obtained from constructively describable infinite iterated function
systems. In these cases, for a priori and monotone complexity, the upper
bound coincides (up to an additive constant) with the lower bound, thus
verifying the existence of oscillation-free maximally complex infinite words.Wed, 07 Oct 2020 15:24:44 +0300https://eccc.weizmann.ac.il/report/2016/013#revision2
Revision 1
| Bounds on the Kolmogorov complexity function for infinite words |
Ludwig Staiger
https://eccc.weizmann.ac.il/report/2016/013#revision1The Kolmogorov complexity function of an infinite word $\xi$ maps a natural
number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We
investigate the maximally achievable complexity function if $\xi$ is taken
from a constructively describable set of infinite words. Here we are
interested in linear upper bounds where the slope is the Hausdorff
dimension of the set.
As sets we consider $\Pi_{1}$-definable sets obtained by dilution and sets
obtained from constructively describable infinite iterated function
systems. In these cases, for a priori and monotone complexity, the upper
bound coincides (up to an additive constant) with the lower bound, thus
verifying the existence of oscillation-free maximally complex infiniteThu, 13 Oct 2016 14:11:45 +0300https://eccc.weizmann.ac.il/report/2016/013#revision1
Paper TR16-013
| Bounds on the Kolmogorov complexity function for infinite words |
Ludwig Staiger
https://eccc.weizmann.ac.il/report/2016/013The Kolmogorov complexity function of an infinite word $\xi$ maps a natural
number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We
investigate the maximally achievable complexity function if $\xi$ is taken
from a constructively describable set of infinite words. Here we are
interested in linear upper bounds where the slope is the Hausdorff
dimension of the set.
As sets we consider $\Pi_{1}$-definable sets obtained by dilution and sets
obtained from constructively describable infinite iterated function
systems. In these cases, for a priori and monotone complexity, the upper
bound coincides (up to an additive constant) with the lower bound, thus
verifying the existence of oscillation-free maximally complex infiniteMon, 01 Feb 2016 21:03:30 +0200https://eccc.weizmann.ac.il/report/2016/013