Kolmogorov complexity of strings in a given language

Question

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

Answer 1

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.