# Why can't we search lexicographicaly ordered programs to compute Kolmogrov complexity?

Kolmogrov complexity is known to be uncomputable. Why can't we enumerate all programs of size i = 0 in lexicographical order - if any produce string s, that is the Kolmogrov complexity; if not, increment i and iterate? Won't that prove that no program of length < i generates string s?

The problem with your approach is that some programs never halt, and it's difficult (indeed, uncomputable) to tell whether they do. You can tell if a program outputs $s$ and halts, but you don't know how much to wait before declaring that the program never halts. However, your approach shows that it is possible to write a program that prints upper bounds on the Kolmogorov complexity of a give string, eventually printing the correct upper bound. This doesn't give you the Kolmogorov complexity since you don't know when the program will have printed its final upper bound.