String Cover
Definitions
Let $K(\cdot)$ denote the Komogorov complexity. $2^{<\omega}$ is the set of all binary strings of finite length. $\log$ is the logarithm with base $2$.
For $\sigma\in 2^{<\omega}$, an $(n,c)$-cover of $\sigma$ is a finite set of strings $A_\sigma$ such that
- each string $\tau\in A_\sigma$ extends $\sigma$,
- each infinite binary string $x$ extending $\sigma$ also extends some $\tau\in A_\sigma$,
- for each $\tau\in A_\sigma$, $K(\tau)\leq K(\sigma)+n$,
- $-\log\sum_{\tau\in A_\sigma} 2^{-K(\tau)}\geq K(\sigma)+c$.
The problem
Question. Is is true that for each $c$, there is $n$ such that each string $\sigma\in 2^{<\omega}$ has an $(n,c)$-cover?
Relevant contents
