However, for small strings, the actual complexity you compute starting from any particular model of computation is totally dwarfed by that O(1) padding cost. So, actually computing Kolmogorov complexities of small strings is basically just pointless trivia.
Sometimes I think this distinction between "general" and "specific" is as deep as the whole idea of uncomputability. When someone says "arbitrary Turing machine" it is very difficult for a layman to wrap their head around what this means. No wonder: I'm using the word "arbitrary", which means "random", which means... uncomputable.
Just wanted to note that we have techniques for termination analysis that cover entire classes of programs of arbitrary length, not just specific short programs. See ranking function synthesis for an example. Hell, under some universal computational models, the halting problem is polynomial-time decidable for almost all programs: https://arxiv.org/abs/math/0504351.
Im tempted to debate this... in any programming language you need to use some space to differentiate a literal from code to be executed. So, according to Kolmogorov complexity, wouldn’t the shortest program to print a random number (or 0) be larger than that number?
"While a computer might find some pattern in a string, it cannot find the best pattern. We might find some short program that outputs a certain pattern, but there could exist an even shorter program. "
What "uncomputable" means is that for the general case, there cannot exist a program that is guaranteed to find the Kolmogorov complexity of a given input string. This is because as we enumerate through all Turing machines from smallest to largest, some will not halt, but we can’t know if this is because the program is just running for a very long time or if it is actually going to run forever. In specific cases for short strings, we can often analytically determine whether the program will halt or not. This is also why we know the first few values of the Busy Beaver function, even though it is also uncomputable.