Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$.

Any ideas how to solve this? If I can construct a Turing machine which just uses a shortest program for one of the strings $y$ or $z$, for example $y$, and an input of length at most $n/2$ to produce $x$ then the problem would be solved, as then $C(x) \le C(y) + n/2$ and so $C(y) \ge C(x) - n/2 = n - O(1) - n/2 = n/2 - O(1)$. But I have no idea how such an algorithm should work?

This is Exercise 2.2.2 (a) from An Introduction to Kolmogorov Complexity and Its Applications.

  • $\begingroup$ Try the algorithm that first computes $y$ and prints it, and then prints $z$. Since $z$ has length $n/2$, the instruction "then print $z$" has length only $(n/2)+O(1)$. $\endgroup$ – Andreas Blass Jul 24 '15 at 22:37
  • $\begingroup$ That's intuitively clear and simple, but what I have problems with is make this formal. My try, let $U$ be the universal Turing machine such that $C = C_U$, and let $T^z$ be a TM which runs $U$ on its input and then prints $z$, so if $U(p) = y$ then $T^z(p) = U(p)z = yz = x$. So now consider some enumeration $T_1, T_2, \ldots$, then $T^z = T_k$ for some $k$. Then I can put this information, i.e. the $k$ in some way in the input for $U$ together with the program $p$, and hence $C(x) \le \mbox{length for coding }k + C(y)$. By this enumeration the way $z$ is hardcoded into $T_k$ gets lost... $\endgroup$ – StefanH Jul 24 '15 at 23:24
  • $\begingroup$ I think you want to arrange for the input to encode both the program for computing $y$ and the string $z$. Unfortunately, you can't just concatenate them; you need to tell the machine where the one ends and the other starts. That can be done with a logarithmic number of additional bits, to tell how long the first part of the concatenation is. I don't immediately see a way to avoid that additional $\log n$. $\endgroup$ – Andreas Blass Jul 25 '15 at 1:20
  • $\begingroup$ Yes,okay if this is not possible I need to hardcode it. But how to encode this into a TM just using $n/2$ additional bits? I can modify a TM by adding enough states and tupels to print $z$ at the end, but in each bit based encoding I can think of this needs more then $n/2$ bits (because for example the encoding need to be self-delimiting between tupels or if I fix the size of an encoded tupel it depends on the number of tupels). The problem is similar if you suppose you can just print one token a time, then "print z" is not possbile, instead "print z_1,,...,print z_k" has length $7\cdot n/2$. $\endgroup$ – StefanH Jul 25 '15 at 11:41
  • $\begingroup$ You don't need to code for a Turing machine; you need to code for a universal machine. Notice first that there is a non-universal (in fact very far from universal) machine that just prints its input. For this ridiculous machine, the length of a program that prints z is just the length of z. Therefore, a universal machine must have a program that prints z and has length bounded by the length of z plus a constant. $\endgroup$ – Andreas Blass Jul 25 '15 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.