4 ms·
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
by superposeur 3mo ago
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.
- pwdisswordfishq 3mo agoHow long is the program which enumerates all N-digit programs?
- doctor_phil 3mo agoI 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 3mo agoOk got it, thanks.