2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ My thoughts might be more confusing than helpful, I wish just to have some tips on how to solve it $\endgroup$ – Phil Moesch Sep 29 '15 at 21:21
  • 1
    $\begingroup$ 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? $\endgroup$ – usul Sep 30 '15 at 12:51
  • $\begingroup$ I added my thoughts, can you have a look and tell me where the problem is ? $\endgroup$ – Phil Moesch Sep 30 '15 at 14:49
  • $\begingroup$ Hint: this is true for every computable language. $\endgroup$ – Yuval Filmus Sep 30 '15 at 15:08
  • $\begingroup$ 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 $\endgroup$ – Phil Moesch Sep 30 '15 at 15:26
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ good answer, but are you sure that, given n, it is possible to output the word Xn ? we might need to know i and j $\endgroup$ – Phil Moesch Sep 30 '15 at 16:17
  • $\begingroup$ You haven't told us the definition of $x_n$, but any reasonable definition will be computable. $\endgroup$ – Yuval Filmus Sep 30 '15 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.