<p>Chaitin  in his 1976 paper</p>

<p><em>Chaitin, Gregory J.</em>, <a href="http://dx.doi.org/10.1016/0304-3975(76)90005-0" rel="noreferrer"><strong>Information-theoretic characterizations of recursive infinite strings</strong></a>, Theor. Comput. Sci. 2, 45-48 (1976). <a href="https://zbmath.org/?q=an:0328.02029" rel="noreferrer">ZBL0328.02029</a>.</p>

<p>studied sets such that there exists  b ∈ℕ  with</p>

<p><span class="math-container">$$\forall n\quad C(A\upharpoonright n)\leq C(n)+b.$$</span></p>

<p>where <span class="math-container">$C$</span> denotes the plain Kolmogorov complexity. These sets are known as C-trivial sets. Chaitin showed they coincide with the computable sets.</p>

<p>Interestingly, this is not so for the prefix-free Kolmogorov complexity version, the <a href="https://en.wikipedia.org/wiki/K-trivial_set" rel="noreferrer">K-trivial sets</a>.</p>

CC BY-SA 4.0
2019-01-04T19:19:36.730Z
Great! I found the proof for the "$\Rightarrow$" direction of the hypothesis in one of the references. Independently: In your answer, shouldn't it be $C(A) \leq C(n) + b$ (without conditioning on n)?
Julius Kunze
CC BY-SA 4.0
2019-01-04T20:00:06.653Z
It's the first $n$ bits of $A$
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2019-01-04T20:46:25.073Z
Makes sense! I misinterpreted the notation.
Julius Kunze
CC BY-SA 4.0
2018-12-31T23:56:23.027Z
2018-12-31T23:56:23.027Z
Bjørn Kjos-Hanssen
<p><strong>Disclaimer:</strong> 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.</p>

<p><strong>Background/Motivation:</strong> 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. <a href="http://www.cs-114.org/wp-content/uploads/2015/01/Elements_of_Information_Theory_Elements.pdf" rel="nofollow noreferrer">[Elements of Information Theory, p. 154]</a> 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.</p>

<p>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?</p>

<p>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.</p>

<p>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?</p>

<p><strong>What I found in literature:</strong> It is shown that a sequence is Martin-Löf random iff there is a constant <span class="math-container">$c$</span> so that there are infinitely many initial segments with complexity greater than <span class="math-container">$n - c$</span> where <span class="math-container">$n$</span> is the segment length. <a href="https://arxiv.org/pdf/math/0110086.pdf" rel="nofollow noreferrer">[Randomness, p. 18]</a></p>

<p>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). <a href="https://www.math.uni-heidelberg.de/logic/merkle/ps/JCSS-stoch.pdf" rel="nofollow noreferrer">[The complexity of stochastic sequences]</a></p>

<p><strong>What's missing for a proof:</strong></p>

<p><span class="math-container">$\Leftarrow$</span>:
Assume a sequence is computable. We know that a program <code>generate_bit(n)</code> exists that generates any bit of the sequence. Now, we can build a program <code>generate_initial_segment(n) = concat(map(1..n, generate_bit))</code> that, given the segment length <span class="math-container">$n$</span>, generates the initial segment up to position n by invoking <code>generate_bit</code> <span class="math-container">$n$</span> times and concatenating the results. The Kolmogorov complexity of this task is therefore bounded by the length of this program. ☐</p>

<p><span class="math-container">$\Rightarrow$</span>: I struggle to prove/disprove this direction, namely: If initial segment complexity is bounded, is a sequence always computable?</p>

<p>Update: The last two pages of <a href="https://www.sciencedirect.com/science/article/pii/S0019995869905385/pdf?md5=5ff60459e171a92caef1156280e1ce2c&amp;pid=1-s2.0-S0019995869905385-main.pdf" rel="nofollow noreferrer">A variant of the Kolmogorov concept of complexity</a> prove this direction.</p>

CC BY-SA 4.0
2018-12-31T11:09:14.237Z
you may find this paper useful: https://homepages.cwi.nl/~paulv/papers/handbooklogic07.pdf
Avi Tal
CC BY-SA 4.0
2018-12-31T19:44:28.190Z
Also this can be useful: [Kolmogorov Complexity of Initial Segments of Sequences and Arithmetical Definability](https://www.sciencedirect.com/science/article/pii/S0304397511004993), George Barmpalias and Charlotte Vlek
Marzio De Biasi
<computability><it.information-theory><kolmogorov-complexity>
Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?
Julius Kunze
# Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?

(Asked by: username_0 on 2018-12-31)

**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]](http://www.cs-114.org/wp-content/uploads/2015/01/Elements_of_Information_Theory_Elements.pdf) 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]](https://arxiv.org/pdf/math/0110086.pdf)

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]](https://www.math.uni-heidelberg.de/logic/merkle/ps/JCSS-stoch.pdf)

**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](https://www.sciencedirect.com/science/article/pii/S0019995869905385/pdf?md5=5ff60459e171a92caef1156280e1ce2c&pid=1-s2.0-S0019995869905385-main.pdf) prove this direction.

**Tags:** computability, it.information-theory, kolmogorov-complexity

> **Comments:**
> **username_1**: you may find this paper useful: https://homepages.cwi.nl/~paulv/papers/handbooklogic07.pdf  
> **username_2**: Also this can be useful: [Kolmogorov Complexity of Initial Segments of Sequences and Arithmetical Definability](https://www.sciencedirect.com/science/article/pii/S0304397511004993), George Barmpalias and Charlotte Vlek  

---

## 1 answers

### Answer by username_3 on 2018-12-31. Score: 7 | Accepted answer

Chaitin in his 1976 paper

*Chaitin, Gregory J.*, [**Information-theoretic characterizations of recursive infinite strings**](http://dx.doi.org/10.1016/0304-3975(76)90005-0), Theor. Comput. Sci. 2, 45-48 (1976). [ZBL0328.02029](https://zbmath.org/?q=an:0328.02029).

studied sets such that there exists b ∈ℕ with

$$\forall n\quad C(A\upharpoonright n)\leq C(n)+b.$$

where $C$ denotes the plain Kolmogorov complexity. These sets are known as C-trivial sets. Chaitin showed they coincide with the computable sets.

Interestingly, this is not so for the prefix-free Kolmogorov complexity version, the [K-trivial sets](https://en.wikipedia.org/wiki/K-trivial_set).

> **Comments:**
> **username_0**: Great! I found the proof for the "$\Rightarrow$" direction of the hypothesis in one of the references. Independently: In your answer, shouldn't it be $C(A) \leq C(n) + b$ (without conditioning on n)?  
> **username_3**: It's the first $n$ bits of $A$  
> **username_0**: Makes sense! I misinterpreted the notation.  

---

