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$?

  • 1
    $\begingroup$ 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. $\endgroup$ Apr 9, 2018 at 7:27
  • $\begingroup$ 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. $\endgroup$ Apr 9, 2018 at 7:35

1 Answer 1


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$.

  • $\begingroup$ 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. $\endgroup$ Apr 9, 2018 at 7:33
  • $\begingroup$ Forgive my ignorance, but I have never heard this term. What's a self terminating encoding? $\endgroup$
    – Ariel
    Apr 9, 2018 at 7:54
  • $\begingroup$ 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. $\endgroup$ Apr 9, 2018 at 7:56
  • 1
    $\begingroup$ 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). $\endgroup$ Apr 9, 2018 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.