2 ms·
>I can't start a program that prints all strings and claim I've achieved ideal compression because the desired output is among one of the strings printed. I do
by vba616 4y ago
>I can't start a program that prints all strings and claim I've achieved ideal compression because the desired output is among one of the strings printed.
I don't follow why this is an example of run time mattering. It sounds like an example of not including crucial information in your "compressed" output to enable decoding. You'd have to have a pointer into your sequence.
Also, why wouldn't consideration of run time be a free choice people make? I vaguely remember trying some allegedly state of the art compressors and finding them extremely slow. Probably in the PPM family. Theoretically, people are sometimes interested in the maximum compression no matter how much it takes in resources.
- svnt 4y agoIf at the fastest speed a computer can physically operate the program would take longer than the expected duration of the universe, I believe we can safely say it does not usefully represent the information, even though in mathematical relationship it may seem to. Less absurdly, if the program takes longer to run than the MTBF of the computer it operates on, we can say the same thing with some probability. It’s a roundabout way of saying that what seems to work in math isn’t always possible useful or functional in material reality. Since Kolmogorov seems to be pointing in this direction of blurring computation in material reality with mathematical information it seems worth considering.