Is checking if the length of a C program that can generate a string is less than a given number decidable?

Question

I was given this question:

Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable?

With respect to decidability, I only know about the Halting Problem and just learned about Rice's Theorem while searching online (though I don't think it can be applied here?). I couldn't reduce the problem to any undecidable problem I know about. Thanks in advance for any help

Answer 1

The length of the smallest C program that generates a given string is known as the Kolmogorov complexity of the string. One of the basic properties of Kolmogorov complexity is its undecidability.