<p>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.</p>

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

CC BY-SA 2.5
2011-01-19T20:30:28.890Z
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
CC BY-SA 2.5
2011-01-20T00:29:06.943Z
You can assign $0$ to $xx$ and something larger for $x$ and still have a universal model.
Kaveh
CC BY-SA 2.5
2011-01-19T17:31:33.250Z
2011-01-19T17:31:33.250Z
Chad Brewbaker
<p>@Tsuyoshi:</p>

<p>I didn't understand well your proof.</p>

<p>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 <strong>string</strong> $s$ on it.</p>

<p>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 <strong>fewer</strong> states than $TM_{s}$ that "prints" the string $s = 1^{2^n}$ ?</p>

<p>Can your proof be applied to Kolmogorov complexity on TMs ?</p>

<p><strong>OK! I GOT IT</strong> ... 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!</p>

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

CC BY-SA 2.5
2011-01-21T14:40:29.887Z
To [write a comment](http://cstheory.stackexchange.com/privileges/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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-21T02:10:35.643Z
2011-01-21T02:39:05.673Z
2011-01-21T02:39:05.673Z
Marzio De Biasi
<p>I am no expert on Kolmogorov complexity, but I think that such <i>x</i> can be constructed for every complexity function K as follows.  Since 1, 11, 1111, 11111111, …, 1<sup>2<sup><i>n</i></sup></sup>, … is an encoding of a natural number <i>n</i>, K(1<sup>2<sup><i>n</i></sup></sup>) cannot be o(log <i>n</i>).  However, when <i>n</i>=2<sup><i>m</i></sup>, obviously K(1<sup>2<sup><i>n</i></sup></sup>)=K(1<sup>2<sup>2<sup><i>m</i></sup></sup></sup>)=O(log <i>m</i>)=O(log log <i>n</i>).  Therefore the sequence K(1), K(11), K(1111), K(11111111), …, K(1<sup>2<sup><i>n</i></sup></sup>), … cannot be weakly monotonically increasing, which means that there exists a string <i>x</i> in the form 1<sup>2<sup><i>n</i></sup></sup> such that K(<i>xx</i>) &lt; K(<i>x</i>).</p>

CC BY-SA 2.5
2011-01-19T17:36:41.930Z
@Tsuyoshi, Is there an incompressible string $x$ such that $K(xx)\lt K(x)$?
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-01-19T20:34:49.680Z
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
CC BY-SA 2.5
2011-01-19T21:19:25.983Z
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
CC BY-SA 2.5
2011-01-19T22:17:16.440Z
@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?](http://cstheory.stackexchange.com/questions/1718/which-definition-of-asymptotic-growth-rate-should-we-teach)
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-19T22:21:41.080Z
@turkistany: I do not know the answer.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-19T22:31:30.533Z
@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
CC BY-SA 2.5
2011-01-20T08:51:43.400Z
@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
CC BY-SA 2.5
2011-01-19T15:58:02.293Z
2011-01-21T00:40:08.423Z
2011-01-21T00:40:08.423Z
Tsuyoshi Ito
<p>Let $K(x)$ denote the Kolmogorov complexity of a string $x$. Do there exist a string such that $K(xx)&lt;K(x)$. (Here $xx$ is the concatenation of $x$ with itself). A similar but different question was asked <a href="https://cstheory.stackexchange.com/questions/4292/kolmogorov-complexity-of-d-and-dd">here</a>, but the counterexample given in the answer to that question doesn't work for this one.</p>

<cc.complexity-theory><kolmogorov-complexity>
Do there exist x such that K(xx)<K(x), where K is Kolmogorov complextity.
Sune Jakobsen
# Do there exist x such that K(xx)<K(x), where K is Kolmogorov complextity.

(Asked by: username_0 on 2011-01-19)

Let $K(x)$ denote the Kolmogorov complexity of a string $x$. Do there exist a string such that $K(xx)here, but the counterexample given in the answer to that question doesn't work for this one.

**Tags:** cc.complexity-theory, kolmogorov-complexity


---

## 3 answers

### Answer by username_4 on 2011-01-19. Score: 20 | Accepted answer

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, …, 12*n*, … is an encoding of a natural number *n*, K(12*n*) cannot be o(log *n*). However, when *n*=2*m*, obviously K(12*n*)=K(122*m*)=O(log *m*)=O(log log *n*). Therefore the sequence K(1), K(11), K(1111), K(11111111), …, K(12*n*), … cannot be weakly monotonically increasing, which means that there exists a string *x* in the form 12*n* such that K(*xx*) < K(*x*).

> **Comments:**
> **username_5**: @Tsuyoshi, Is there an incompressible string $x$ such that $K(xx)\lt K(x)$?  
> **username_0**: 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.  
> **username_6**: 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".  
> **username_4**: @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?](http://cstheory.stackexchange.com/questions/1718/which-definition-of-asymptotic-growth-rate-should-we-teach)  
> **username_4**: @turkistany: I do not know the answer.  
> **username_4**: @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).  
> **username_7**: @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.  

---

### Answer by username_1 on 2011-01-19. Score: 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: You can assign $0$ to $xx$ and something larger for $x$ and still have a universal model.  

---

### Answer by username_3 on 2011-01-21. Score: 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)

> **Comments:**
> **username_4**: To [write a comment](http://cstheory.stackexchange.com/privileges/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.  

---

