16
$\begingroup$

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.

$\endgroup$
20
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @Tsuyoshi, Is there an incompressible string $x$ such that $K(xx)\lt K(x)$? $\endgroup$ – Mohammad Al-Turkistany Jan 19 '11 at 17:36
  • $\begingroup$ 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. $\endgroup$ – Sune Jakobsen Jan 19 '11 at 20:34
  • 1
    $\begingroup$ 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(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". $\endgroup$ – Abel Molina Jan 19 '11 at 21:19
  • $\begingroup$ @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? $\endgroup$ – Tsuyoshi Ito Jan 19 '11 at 22:17
  • 1
    $\begingroup$ @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. $\endgroup$ – domotorp Jan 20 '11 at 8:51
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sune Jakobsen Jan 19 '11 at 20:30
  • $\begingroup$ You can assign $0$ to $xx$ and something larger for $x$ and still have a universal model. $\endgroup$ – Kaveh Jan 20 '11 at 0:29
1
$\begingroup$

@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)

$\endgroup$
  • $\begingroup$ To write a comment on a post made by someone other than you which is not an answer to your question, you need reputation point at least 50. $\endgroup$ – Tsuyoshi Ito Jan 21 '11 at 14:40

Your Answer

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

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