[superposeur]

I don’t understand the claim that Kolmogorov lower bounds are uncomputable. Three digit strings are unlikely to run as a program so surely 3 is a lower bound on Kolmogorov of the first million digits of pi, no? To tighten bound, one would need to try out every 4-digit program, every 5-digit program, and so on. Either these produce the first million digits of pi or they don’t when the program is run, so each possibility is checkable in finite time, no? There must be something I’m missing here.

[doctor_phil]

I agree, producing a lower bound is possible. It's practically very hard to give a good lower bound though. Many programs do not terminate, so we don't know if they do produce the right output eventually. In practice the best that has been done on Turing machines is that we have now proved which 5-state machines halt and which don't. So proving any lower bounds larger than that is practically impossible.

[superposeur]

Ok got it, thanks.

[pwdisswordfishq]

How long is the program which enumerates all N-digit programs?