This question was inspired by Sune Jakobsen's question and Tsuyoshi's answer. In Kolmogorov-complexity, a string is incompressible if $K(S) \ge |S|$.
Is there incompressible string $S$ such that $K(SS) \lt K(S)$? Is there an infinite set of such strings? What is the theoretical consequence if such infinite set of strings does exist?
A rough argument that there should be infinitely many such strings is as follows.
Consider a machine $M$ that first left-pads its input with zeroes out to some known length $2f(|T|)$ (we will specify $f$ below), then repeatedly performs some length-preserving and random-looking operation on it, halting only when it has produced (essentially by accident) a string consisting of two copies of the same string. It is not required to halt for every input. When it does, the output it produces from input $T$ will have complexity satisfying $K(SS) \approx K(T) + K_M$ for some $K_M$, as long as $f(|T|)$ is large enough, and $S$ will have length $f(|T|)$. The string $S$, moreover, will have complexity $K(S) \approx K(SS) + K_C$ for some $K_C$. The key final step is to choose the right $f(|T|)$. It must be large enough to ensure that $SS$ is best described as "the output of $M$ applied to $T$", but small enough to ensure that the description of $S$ as "half the output of $M$ applied to $T$" is not less than $|S| = f(|T|)$. Taking $f(|T|)=|T|+K_M+K_C-1$ should work. We conclude that arbitrarily long incompressible inputs $T$, if they halt, will typically produce outputs $SS$ such that $K(SS) < K(S)$ and such that $S$ is incompressible. The machine $M$ could do any number of things; for instance, the machine $M$ that squares its input and then discards every other bit of the result would probably work.
The answer depends on the universal Turing-machine used to define K. Note that a Turing-machine is called universal, if on input "T", x, where T is a some standard description of a Turing-machine T, it outputs T(x) but we do not know anything about its behaviour on other inputs.
If on every other input it halts, then such strings exist as shown by mjqxxxx.
Howoever, suppose that on input "zip("T")", x, where zip("T") is a more efficient description of T, it uncomputes T(X) and if it is of the form SS and the length of S is about twice as long as |"zip("T")", x|, then it outputs S, otherwise it does not output anything. (On other forms of input, it does not do anything.) This second rule will never give to a string a shorter description than its length, so it will not reduce the complexity of SS type strings. But if we get short description using the first rule for SS, then we get a shorter for S using this second rule.
Note that I did not specify "T" or zip, but it is clear that there are compressible descriptions.
@mjqxxxx:
In your proof you start from (pseudo) randomly generating $SS$ running $M$ on an arbitrary incompressible input $T$, but this does not assure that $S$ can be generated in a similar way by another "shuffler" $M_{2}$ made with fewer states than $M$ and running on an incompressible input $T_2$ and $|T_2| \leq |T|$?
$|S| <= K(S) = |M_2| + |T_2| < K(SS) = |M| + |T| \leq |M_2| + |T_2| + |$states for "make a copy of the tape"$|$
And what is the mening of the symbol $\approx$ in your proof ?
When you say: "the string $S$, moreover, will have complexity $K(S) \approx K(SS)+K_C$" you should write: $K(S) \leq K(SS) + c$
(for all $S$, $| K(SS) - K(S) | < c$ because $SS$ can be built from $M_S$ adding a few states that "make a copy of the content of the tape" and $S$ can be built from $M_{SS}$ adding a few states that "split the content of the tape in 2 halves")
This is not an answer, it contains some "practical" thoughts on the question :-). I did some investigations using Java as "target" language and defining $K(s)$ as the length of a function in the form:
String s(){<return a STRING_EXPR>}
and such that s() == $s$
Obviously we can build:
String s(){return"$s$";}
So, for every string $s$, $K(s) <= |s| + 21$ (assuming that no special character is in the string)
I'm trying to figure out an incompressible string $s$ (i.e. $K(s)>=|s|$) for which $K(ss) < K(s)$
... but didn't find it ... any ideas?
I've made some tries with small strings, for example $r = a^{28} = aaaaaaaaaaaaaaaaaaaaaaaaaaaa$
String r(){return"aaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
String r(){String x="aaaaaaa";return x+x+x+x;} // << K(r)=46
aaaaaaaaaaaaaaaaaaaaaaaaaaaa // << |r|=28
$r$ is incompressible ( $K(r)>|r|$ ) ... but didn't find a way to make $K(rr)<K(r)$
Furthermore if such string exist, then $K(r) - K(rr)$ cannot be "too large", indeed we can build:
CODE_FOR_R: function r(){return<SOME_SHORT_EXPR_FOR_RR>.substring($N$);}
where $N$ is half the length of $rr$