1
$\begingroup$

The proof in the wikipedia article for the uncomputability of Kolmogorov complexity uses the fact that there are strings of arbitrarily large Kolmogorov complexity. What if we restrict to a finite domain so this no longer holds? Specifically, what if I am only interested in strings of length $\le N$, is there an algorithm $M_N$ for computing Kolmogorov complexity for all these strings? As long as $$ |M_N| \ge max \{K(s)| s \in \Sigma^i, i \le N\}\,, $$ it seems like it would at least escape the contradiction from Wikipedia.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The answer is "yes", i.e., for every fixed $N$, there is an algorithm $M_N$ that, given an input string $s$ (on some fixed alphabet $\Sigma$) of length at most $N$, returns the Kolmogorov complexity of $s$. You might find the argument a bit unsatisfactory though, as it is not constructive.

Let $s_1, s_2, \dots$ be the strings in $\bigcup_{i=0}^N \Sigma^i$ and let $k_i$ be the Kolmogorov complexity of $s_i$. $M_N$ determines which of the (finitely many) strings $s_i$ matches the input string, and returns $k_i$. Notice this approach only works because the set of input strings for which we need to answer correctly is finite (since algorithms are required to have a finite amount of instructions).

$\endgroup$
6
  • 3
    $\begingroup$ More generally, anything is computable on a finite domain. $\endgroup$ Commented Mar 11, 2022 at 19:14
  • 1
    $\begingroup$ Thanks, you're right it's a bit unsatisfying though. If $M_N$ is just a lookup table, doesn't this mean we need to know all the $k_i$'s in advance? $\endgroup$
    – ludog
    Commented Mar 12, 2022 at 9:07
  • $\begingroup$ Yeah, essentially $M_N$ just consults a lookup table. You don't need to know the $k_i$s to show the *existence* of $M_N$, you just need to show that there is some choice of $k_i$ that makes the algorithm work. In your problem the input is $s$, $|s|\le N$ and the output is $K(s)$. You might be thinking of the problem of finding $M_N$. There the input would be $N$ and the output would be a description of an algorithm $M_N$ that, on input $s$, $|s|\le N$ returns $K(s)$. The latter problem is clearly undecidable since it allows you to find $K(s)$ of any string $s$ by first computing $M_{|s|}$. $\endgroup$
    – Steven
    Commented Mar 12, 2022 at 9:52
  • $\begingroup$ Yes, I guess the problem of finding $M_N$ is what I'm thinking of. Could the same not be said about this problem though? The only reason this is clearly uncomputable is that now $N$ is unbounded, but suppose I only want to be able to find $M_N$ for all $N$ up to some fixed number? $\endgroup$
    – ludog
    Commented Mar 13, 2022 at 11:43
  • $\begingroup$ Then the same strategy still works, there is an algorithm that takes in input $N$ and consults a lookup table to output $M_N$. As soon as $N$ is not upper bounded by some fixed constant then the problem becomes undecidable again. $\endgroup$
    – Steven
    Commented Mar 15, 2022 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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