Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity.
Background/Motivation: Coming from information theory, I recently learned about a connection of entropy and Kolmogorov complexity: Loosely speaking, entropy of a random variable is the expected rate at which the Kolmogorov complexity of a long sample sequence increases per sample. [Elements of Information Theory, p. 154] Kolmogorov complexity can therefore capture the notion of entropy, but it is more general than that. Hereby, and in the following, whenever I write complexity, I implicitly refer to the complexity given the length of the output.
For non-zero entropy, the Kolmogorov complexity of initial segments of an infinite sequence of samples from a random variable is therefore unbounded. I was wondering whether this is equivalent to the fact that an infinite sequence of samples is uncomputable. This led me to the hypothesis in the title: Is a binary sequence computable if and only if the Kolmogorov complexity of its initial segments is bounded?
If the hypothesis was true, then computability could be understood as an indicator that the "amount of information" in a sequence is finite. In some sense, the initial segment complexities would allow a more finely graded characterization of infinite sequences than just "computable" and "uncomputable". We could get a notion of "information content" and "information rate" of infinite sequences by analyzing the size of the bound or, in the unbounded case, the rate/type of growth, as in the entropy case above. My question boils down to whether "computable" and "uncomputable" are regions on this scale.
If the hypothesis is true, I'd be interested in whether this perspective is useful for TCS research. If yes, are there references elaborating this idea? If not, why not?
What I found in literature: It is shown that a sequence is Martin-Löf random iff there is a constant $c$ so that there are infinitely many initial segments with complexity greater than $n - c$ where $n$ is the segment length. [Randomness, p. 18]
This means that random sequences have unbounded initial segment complexity. Since they are not computable, the hypothesis is true at least for this case. If I am not mistaken, a similar argument could even be made for a weaker form of randomness, since Mises-Wald-Church random sequences cannot have initial segment complexity of O(log n). [The complexity of stochastic sequences]
What's missing for a proof:
$\Leftarrow$:
Assume a sequence is computable. We know that a program generate_bit(n) exists that generates any bit of the sequence. Now, we can build a program generate_initial_segment(n) = concat(map(1..n, generate_bit)) that, given the segment length $n$, generates the initial segment up to position n by invoking generate_bit $n$ times and concatenating the results. The Kolmogorov complexity of this task is therefore bounded by the length of this program. ☐
$\Rightarrow$: I struggle to prove/disprove this direction, namely: If initial segment complexity is bounded, is a sequence always computable?
Update: The last two pages of A variant of the Kolmogorov concept of complexity prove this direction.
