# Kolmogorov complexity of prefixes of computable sequences

Let the characteristic sequence of a set $A ⊆ \mathbb{Z^+}$ be the following infinite binary sequence:

$$χ_A = b_1b_2b_3\ldots,$$

whose $n$th bit is 1 if $n ∈ A$ And 0 otherwise. Write $χ_{A,n}$ for the first $n$ bits of $χ_A$.

Prove for every decidable set $A \subseteq \mathbb{Z^+}$ there is a constant $c ∈ \mathbb{N}^+$ such that for all $n ∈ \mathbb{Z}^+$ the Kolmogorov complexity of $\chi_{A,n}$ satisfies

$$C(χ_{A,n})≤\log n+c.$$

Since $A$ is decidable there is a lexicograhic enumerator. Given that, how would I construct a Turing machine $\pi_A$ satisfying $U(\pi_A)= χ_{A,n}$, where $U$ is the universal Turing machine, whose complexity is at most $\log n+c$?

• This is a rather basic question in Kolmogorov complexity. Indeed, in some textbooks this result is proved rather than given as an exercise. I suggest spending some more time on it and trying to solve it on your own. – Yuval Filmus Apr 9 '18 at 7:27
• my professor is diverging from the topics covered by Kozen, but covered in Sipser. Hard to find examples, did not know this was a common question. – ZeroDay Fracture Apr 9 '18 at 7:35

## 1 Answer

Let $D$ be a decider for $A$, then in order to determine $\mathcal{X}_{A,n}$ it is enough to specify $n$ and an encoding of $D$. Given $D,n$, you can loop over all integers $i\in [n]$ and check whether or not $i\in A$ by simulating $D(i)$. Thus, the overall description of $\mathcal{X}_{A,n}$ consists of $n$, the encoding of $D$ and the encapsulating machine $M$ (described above) which uses $D,n$ to output $\mathcal{X}_{A,n}$. $n$ contributes at most $\log n$ bits to the description, and $D,M$ have some encoding of length $c$ independent of $n$, bounding the overall description length by $\log n + c$.

• You should be careful here when saying that $n$ takes $\log n$ bits to encode. This is only possible if the encoding is not self-terminating. – Yuval Filmus Apr 9 '18 at 7:33
• Forgive my ignorance, but I have never heard this term. What's a self terminating encoding? – Ariel Apr 9 '18 at 7:54
• Suppose that you want to encode two numbers $a,b$. Can you do it using only $\log a + \log b$ bits? Not really, since you won't be able to separate the two strings. However, you could use a prefix code to encode $a$ in (let's say) $\log a + 2\log\log a$ bits, for a total cost of $\log a + 2\log\log a + \log b$. You could encounter the same problem here - unless you encode $n$ as the very last bit of the program, in which case you can tell where the encoding terminates since you know the extent of the string. – Yuval Filmus Apr 9 '18 at 7:56
• There are two variants of Kolmogorov complexity, one in which the set of allowed programs has to form a prefix code, and one without this constraint. They behave slightly differently. Often one is denoted $C$ and the other $K$ (not sure which is which). – Yuval Filmus Apr 9 '18 at 7:57