What is the relationship between Kolmogorov Complexity and Turing Machines?

Question

I am trying to understand the following definition -

Let M be a TM, and let $x \in \sum^*$. The plain Kolmogorov complexity of x with respect to M is - $C_{M}(x) = min\{|\pi|:\pi \in \sum^* \land M(\pi) = x \}$

I understand both Turing Machines and Kolmogorov complexity in general. However, I haven't been able to find sources that explain how to combine both of them.

Answer 1

First of all, this definition is linked to the machine $M$, there is another definition that is more general: the absolute Kolmogorov complexity. This more general definition is the one we can use to make full sense of the informal way to see it:

The complexity of some string is the length of the shorter program we can use to generate it.

So, what your definition says?

Let review the elements of this definition:

1. The Turing Machine $M$, that can be associated to its program $P$, a set of quadruples of strings of the form $q_ia_ja_kq_l$.

2. An alphabet $\Sigma$ with letters $\{a_0, ..., a_n\}$. We can for example consider this alphabet to be the binary letters $\{0,1 \}$.

3. The set of all strings over the alphabet $\Sigma$, denoted by $\Sigma^*$.

4. The string x element of $\Sigma^*$.

5. The input string $\pi$ that is also element of the set of strings $\Sigma^*$.

We could write this definition in this cleaner way (letting the $\pi \in \Sigma^*$ in the hypothesis of the definition) :

$$ C_M(x) = \min \{ |\pi| : M(\pi) = x \}.$$

This says that the complexity relative to $M$ of the string $x$ is the length of the shorter input given to the Turing Machine $M$ that generates $x$. (note the difference with the first informal way of seeing we gave up there).

Lets make some examples. You can think the case when the machine $M$ is the machine that implements the function $f(n) = 2^n$. We can simplify this example and represent numbers in this specific machine using the standard binary representation of numbers (this is not convenient way to represent it in general thought, for we can't associate a number for the string 01). So we give some string like 100000 (32 in decimal) and $M$ gives to us:

$$ 100000000000000000000000000000000$$

(i.e. 1 followed by 32 zeros). Because there isn't another shorter input that generates it, we can say that:

$$ C_M(100000000000000000000000000000000) = 100000.$$

Obviously, there are flaws when we restrict the complexity to this machine. One is that complexity function $C_M$ defined upon it is not defined for odd numbers. A better machine is the universal machine $U$.

As it is universal, it can interpret the input it receives as programs (yes, now we can make some sense of the informal definition we gave in the beginning). And $U$ can at least find one program-input $\pi$ that generates the string $x$: the monotonous program-input that prints $x$ and stops. (But in general $C_U$ is not a partial computable function)

This is the idea behind the absolute Kolmogorov complexity, and the informal construction behind it. But the construction is not complete yet, we have to proof a certain theorem called the invariance theorem. This theorem informally says that you can pick up a universal machine that, even for some reason is not efficient for some task (think of a program language that is cumbersome to operate strings), will not stay behind the optimal universal machine for the task (some program language that operates natively with strings), at least not by a constant.

For the literature, besides Chaitin articles, there is a technical reference called An Introduction to Kolmogorov Complexity and Its Applications, by Li and Vitányi.