Is checking if the length of a C program that can generate a string is less than a given number decidable?
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.