# Kolmogorov complexity of strings in a given language

Consider the language

$$L = \{1^i 0^j 1^k \mid i + j = 2k, k ≥ 1\}\,,$$

and let $x_n$ be the canonical $n$'th word in $L$. My problem involves proving that the Kolmogorov complexity of $x_n$ can be bounded by

$$K(x_n) \leq c + 2\log_2 |x_n|$$

for some constant $c$.

My ideas :

(please note that I'm not writing this in a formal way, I am neglecting some constants/factors)

we want to be able to compress the string given by x_n above, thus we could set :

$$K(x_n) = K(1^i) + K(0^j) + K(1^k)$$

(to do this compression I evaluate that only i, j and k need to be compressed, thus we only consider the length of the binary representation of i,j and k as the upper-bound of their corresponding Komolgorov Complexity)

$$\leq log_2 (i) + log_2 (j) + log_2 ((i+j)/2) + C$$

$$= log_2 (i) + log_2 (j) + log_2 (i+j) - 1 + C$$

$$= log_2 (i^2j + ij^2) + K$$

Now we might want to evaluate the length of X_n $$|x_n| \leq i + j + k = i + j + (i + j)/2$$

now to show the supposition we just need to show that :

$$log_2 (i^2j + ij^2) \leq 2log_2 |x_n| = log_2 (|x_n|^2)$$

and this is where I get stuck

• My thoughts might be more confusing than helpful, I wish just to have some tips on how to solve it Sep 29, 2015 at 21:21
• You want to show that each $x_n$ has a pair (Turing machine, input) producing the string $x_n$, with description length $c + \log_2|x_n|$. What is "sufficient information" to output a string in the language?
– usul
Sep 30, 2015 at 12:51
• I added my thoughts, can you have a look and tell me where the problem is ? Sep 30, 2015 at 14:49
• Hint: this is true for every computable language. Sep 30, 2015 at 15:08
• aaah I think I got it, in fact you just need to compress i and j to achieve to compression of X_n, which mean they are sufficient information to output the string Sep 30, 2015 at 15:26

You haven't explained what is meant by the canonical $n$th word, but I assume that there is an algorithm generating all words in $L$, and the canonical $n$th word is just the $n$th word in this list. One such algorithm could go over all possible words in size-lexicographic order, and check for each word whether it belongs to $L$, outputting the words that are in $L$ in size-lexicographic order.
Given such an algorithm, you can construct a new algorithm which gets $n$ and outputs $x_n$. Using the new algorithm, you can generate $x_n$ by running the new algorithm on the input $n$. Since the new algorithm is fixed, it has some size $C$. A prefix-free encoding of $n$ takes $2\log n$ (in fact, you can do almost twice as good), leading to a description length of $C + 2\log n$. (Depending on your definition of Kolmogorov complexity, you might be able to do away with prefix-freedom, and then you can replace $2\log n$ with $\log n$.)
Note that we have only used the fact that the canonical $n$th word is generated by some algorithm which gets $n$ as input. The particular form of $L$ wasn't important.
• You haven't told us the definition of $x_n$, but any reasonable definition will be computable. Sep 30, 2015 at 16:20