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.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
7
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).
answered Jan 19, 2011 at 15:58
-
1$\begingroup$ @Tsuyoshi, Is there an incompressible string $x$ such that $K(xx)\lt K(x)$? $\endgroup$ Commented Jan 19, 2011 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$ Commented Jan 19, 2011 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$ Commented Jan 19, 2011 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$ Commented Jan 19, 2011 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$– domotorpCommented Jan 20, 2011 at 8:51
$\begingroup$
$\endgroup$
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.
-
$\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$ Commented Jan 19, 2011 at 20:30
-
$\begingroup$ You can assign $0$ to $xx$ and something larger for $x$ and still have a universal model. $\endgroup$– KavehCommented Jan 20, 2011 at 0:29
$\begingroup$
$\endgroup$
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)
answered Jan 21, 2011 at 2:10
-
$\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$ Commented Jan 21, 2011 at 14:40