# kolmogorov complexity for finite Language?

In lectures my professor proved that there is no Turing machine that for every x it calculates k(x).

On the other hand, I saw a claim online that for finite language L there is a Turing machine that calculate k(x) for every x in the finite language L.

But how does it work, why is this possible.

This is not a property specific to kolmogorov complexity - it works with any function over strings (no matter what the function is!).

Since $$L$$ is finite, then also the set $$K:=\{(x,k(x))\mid x\in L\}$$ is finite.

Therefore there exists some TM that has the entire set $$K$$ stored in a large table. When the TM is given input $$x$$, it will look through this table and output the appropriate $$k(x)$$.

• Sorry but this made me more confused, read this: "It has been formally proven that one can't compute the Kolmogorov complexity of a string." stackoverflow.com/questions/3836134/…
– Dan
Dec 13, 2021 at 20:40
• In this question you asked "how to compute the Kolmogorov complexity of every string in a finite language $L$". In the link, they answer for "how to compute the Kolmogorov complexity of all possible strings". Those two are totally different questions Dec 13, 2021 at 21:31
• I didn't get that.
– Dan
Dec 14, 2021 at 0:08
• I claim that the one of the strings in L happens to be the lowest counterexample to the Collatz conjecture, and the string is longer than the program which brute-forces the Collatz conjecture. How does a Turing machine calculate k(this string)? there's probably a direct reduction to the halting problem but I am too lazy to find it. Dec 15, 2021 at 0:19
• There is no reduction, if your only task is to compute this value. Since its a single string, then $k(s)$ is some value (doesnt really matter what). Now, I claim there exists a TM which just outputs this $k(s)$ without even computing anything. This TM is hard-wired to output the specific value of $k(s)$, be it $5$, $100$ or $2021$. Dec 15, 2021 at 0:59