# 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. 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. Apr 9 '18 at 7:35

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. Apr 9 '18 at 7:33
• 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. 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). Apr 9 '18 at 7:57