pith. sign in

arxiv: 1410.0310 · v4 · pith:2ECPLYV6new · submitted 2014-09-12 · 💻 cs.IT · math.IT

Some properties of antistochastic strings

classification 💻 cs.IT math.IT
keywords stringsantistochasticcomplexityabsolutelyconditionaldecodingequalserasing
0
0 comments X
read the original abstract

Antistochastic strings are those strings that lack any reasonable statistical explanations. We establish the follow property of such strings: every absolutely non-stochastic string $x$ is "holographic" in the sense that it can be restored by a short program from any its part whose length equals the Kolmogorov complexity of $x$. Further we will show how it can be used for list decoding from erasing and for prove that symmetry of information fails for total conditional complexity.

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.