"In theory you can enumerate all Turing machines of a given length, or all Python programs of a given length, and find the shortest one that does a given task, but the list grows exponentially with length."
Can it be proven that the shortest program is always the fastest?
This is the problem I had when studying mathematics and still have with mathematics to this day: mathematics when stripped and laid bare is just clever transformations, "pouring from hollow into empty", as the old folks' saying goes. What is or are the practical applications of Kolmogorov complexity, how might I be able to turn this to my advantage?
It is rarely the case that the shortest program is the fastest.
To see a simple such phenomenon (very roughly) in the case of Kolmogorov complexity, consider two programs to print a sequence of 0x1000000 zeros.
Program 1:
for i = 1 to 0x10000000:
print 0
Program 2:
i = 0x1 << 28;
for j=1 to i
print 0
(I may be off by a constant, but you get the idea). Program 2 is shorter, since it takes about log 28 bits (the other code has basically constant length), while Program 1 takes about 32 bits (the remaining code being of a different constant length). They both produce the same string. Program 1 is longer, but "faster", since it does not have the left-shift loop.
Philosophically: Program 1 has identified that the string to be printed is a very simple one. Program 2 has exploited the additional fact that the length of the string to be printed, itself is a very simple number, and has a short description. But then it needs additional time to figure out how many zeroes to print, since it needs to decode the length first.
This effect can be amplified with larger constants involved.
Kolmogorov complexity is a "well-defined" notion, hence mathematically nice, it is just that it is not computable. That's bad, but not catastrophic. The halting problem is undecidable, C++ compilation with templates is undecidable [1] - that does not make coding useless.
About the larger problem of dry mathematical textbooks, I agree with you. Some of it just boils down to the fact that the pure and the applied side are often tightly segregated, and very few mathematicians care about both. When you talk to practising mathematicians, you often get a livelier picture.
In most cases the shortest program is the fastest, because most bitstrings are random, and the shortest program just prints the bitstring.
On the other hand, for compressible bitstrings, the shortest program is most likely not going to be the fastest, because you need at least one operation to output each final bit, so since the shortest program is going to be doing more than just printing the output, it's probably going to take longer than just printing the output.
Can it be proven that the shortest program is always the fastest?
This is the problem I had when studying mathematics and still have with mathematics to this day: mathematics when stripped and laid bare is just clever transformations, "pouring from hollow into empty", as the old folks' saying goes. What is or are the practical applications of Kolmogorov complexity, how might I be able to turn this to my advantage?