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