16

Let $K(x)$ denote the Kolmogorov complexity of a string $x$. Do there exist a string such that $K(xx)<K(x)$. (Here $xx$ is the concatenation of $x$ with itself). A similar but different question was asked here, but the counterexample given in the answer to that question doesn't work for this one.

Community
  • 1
Sune Jakobsen
  • 263
  • 1
  • 6

3 Answers3

20

I am no expert on Kolmogorov complexity, but I think that such x can be constructed for every complexity function K as follows. Since 1, 11, 1111, 11111111, …, 12n, … is an encoding of a natural number n, K(12n) cannot be o(log n). However, when n=2m, obviously K(12n)=K(122m)=O(log m)=O(log log n). Therefore the sequence K(1), K(11), K(1111), K(11111111), …, K(12n), … cannot be weakly monotonically increasing, which means that there exists a string x in the form 12n such that K(xx) < K(x).

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
  • 1
    @Tsuyoshi, Is there an incompressible string $x$ such that $K(xx)\lt K(x)$? – Mohammad Al-Turkistany Jan 19 '11 at 17:36
  • I think that $K(1^{2^{2^m}})=O(\log m)$ and K(1^{2^n})=Ω(log n) contradict each other. What he mean is: If $f(n)=o(\log n)$ then $K(1^{2^n})\neq O(f(n))$. Otherwise the proof seems fine. – Sune Jakobsen Jan 19 '11 at 20:34
  • 1
    This seems to work. Indeed, I think it gives you an infinite sequence of such strings. However, either I am misunderstanding something, or the statement of the chain rule for Kolmogorov Complexity that appears in wikipedia(http://en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity) is then wrong.

    Initially I thought that wikipedia's definition might not apply here, as there you have to be able to know where does X end and Y begin, while here this seems not to be required, but when Y = X you can add that to the description in O(1) by saying "split in the middle".

     – Abel Molina Jan 19 '11 at 21:19
  • @Sune: The notation Ω(⋅) has several slightly different definitions. “K(1^2^n)=Ω(log n)” in my answer means “limsup K(1^2^n)/log n > 0,” and it does not contradict “K(1^2^2^m)=O(log m).” I edited the answer to clarify this point. See also Which definition of asymptotic growth-rate should we teach? – Tsuyoshi Ito Jan 19 '11 at 22:17
  • @turkistany: I do not know the answer. – Tsuyoshi Ito Jan 19 '11 at 22:21
  • @Abel: I do not know the exact statement of the chain rule for Kolmogorov complexity (in particular, which definition of the O(⋅) notation is used in Wikipedia). – Tsuyoshi Ito Jan 19 '11 at 22:31
  • 1
    @turkistany and all: Note that it is always true that K(xx)>K(x)-c for some constant, I thought this should be pointed out. This also means that we need a very precise definition of incompressible if we want to study this question. I would guess the answer is again yes, but I don't have a proof. – domotorp Jan 20 '11 at 08:51
2

Yes. Kolomogorov complexity in practice does depend on your model. Turing machine, Java program, C++ program,... if there is an idiosyncrasy in your model that allows for this to happen on a finite set of inputs it is no problem.

The better question is how much of this behavior can you get away with and still have the model be a universal.

Chad Brewbaker
  • 2,359
  • 15
  • 18
  • I think a better question is: Does such x exist for all models? I don't know what a "model" is formally, but it seems that Tsuyoshis answer works for all reasonable programming languages. – Sune Jakobsen Jan 19 '11 at 20:30
  • You can assign $0$ to $xx$ and something larger for $x$ and still have a universal model. – Kaveh Jan 20 '11 at 00:29
1

@Tsuyoshi:

I didn't understand well your proof.

Assume that we pick a standard Turing Machine as "description language" defining $K(s)$ as the number of states of the smallest TM that starts with an empty tape and halts after printing the string $s$ on it.

Did you proved that we can build a $TM_{ss}$ that "prints" the string $ss = 1111...1 = 1^{2^{n+1}}$ on the tape and is built with fewer states than $TM_{s}$ that "prints" the string $s = 1^{2^n}$ ?

Can your proof be applied to Kolmogorov complexity on TMs ?

OK! I GOT IT ... when $n+1 = 2^{m}$ the $TM_{ss}$ can be "powered" with a new "inner loop" (we add some states but we can remove many states that in $TM_{s}$ are needed for "counting" $n$) ... Thanks!

(sorry, but I don't know how to post this as comment)

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127