1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$
5
  • $\begingroup$ 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/… $\endgroup$
    – Dan
    Dec 13, 2021 at 20:40
  • $\begingroup$ 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 $\endgroup$
    – nir shahar
    Dec 13, 2021 at 21:31
  • $\begingroup$ I didn't get that. $\endgroup$
    – Dan
    Dec 14, 2021 at 0:08
  • $\begingroup$ 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. $\endgroup$ Dec 15, 2021 at 0:19
  • 1
    $\begingroup$ 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$. $\endgroup$
    – nir shahar
    Dec 15, 2021 at 0:59

Your Answer

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