solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看2214次
Compression of data streams down to their information content. (arXiv:1710.02092v1 [cs.IT])
来源于:arXiv
According to Kolmogorov complexity, every finite binary string is
compressible to a shortest code -- its information content -- from which it is
effectively recoverable. We investigate the extend to which this holds for
infinite binary sequences (streams). We devise a coding method which uniformly
codes every stream $X$ into an algorithmically stream $Y$, in such a way that
the first $n$ bits of $X$ are recoverable from the first
$I(X\upharpoonright_n)$ bits of $X$, where $I$ is any information content
measure which is either computable or satisfies a certain property. As a
consequence, if $g$ is any computable upper bound on the initial segment \pf
complexity of $X$, then $X$ is computable from an algorithmically random $Y$
with oracle-use at most $g$.If no such computable upper bound is available, the
oracle-use is bounded above by $K(X\upharpoonright_n)+K(n)$. 查看全文>>