On the gap between trivial and nontrivial initial segment prefix-free complexity
M. Baartse and G. Barmpalias
Summary
An infinite sequence $X$ is said to have trivial (prefix-free) initial segment complexity if
$K(X\upharpoonright n)\leq^+ K(0^n)$ for all $n$, where $K$ is the prefix-free complexity and $\leq^+$ denotes inequality modulo a constant.
In other words, if the information in any initial segment of it is merely the information in a sequence of 0s of the same length.
We study the gap between the trivial complexity $K(0^n)$ and the complexity of a non-trivial sequence, i.e.\ the functions $f$ such that
\[
(\star)\ \ K(X\upharpoonright n)\leq^+ K(0^n)+f(n)\ \textrm{for all $n$}
\]
for a non-trivial (in terms of initial segment complexity) sequence $X$.
We show that given any $\Delta^0_2$ unbounded non-decreasing function $f$ there exist uncountably many sequences $X$
which satisfy ($\star$).
On the other hand
there exists a $\Delta^0_3$ unbounded non-decreasing function $f$ which does not satisfy ($\star$)
for any $X$ with non-trivial initial segment complexity.
This improves the bound $\Delta^0_4$ that was known.
Finally we give some applications of these results.