pith. sign in

arxiv: 0809.2965 · v4 · submitted 2008-09-17 · 💻 cs.CC · cs.IT· math.IT

On Time-Bounded Incompressibility of Compressible Strings and Sequences

classification 💻 cs.CC cs.ITmath.IT
keywords boundedcompressibleeveryincompressiblecomplexityinfiniteinitialkolmogorov
0
0 comments X
read the original abstract

For every total recursive time bound $t$, a constant fraction of all compressible (low Kolmogorov complexity) strings is $t$-bounded incompressible (high time-bounded Kolmogorov complexity); there are uncountably many infinite sequences of which every initial segment of length $n$ is compressible to $\log n$ yet $t$-bounded incompressible below ${1/4}n - \log n$; and there are countable infinitely many recursive infinite sequence of which every initial segment is similarly $t$-bounded incompressible. These results are related to, but different from, Barzdins's lemma.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.