# is Kolmogorov complexity computable on a finite domain?

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.

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).
• 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? Mar 12, 2022 at 9:07
• 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|}$. Mar 12, 2022 at 9:52
• 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? Mar 13, 2022 at 11:43
• 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. Mar 15, 2022 at 9:25