4 ms·

You're not considering the exchange for space versus time. A short program may be able to compute the digits of pi to the accuracy you want but you're discounti

You're not considering the exchange for space versus time. A short program may be able to compute the digits of pi to the accuracy you want but you're discounting the runtime and subsequent resources it uses to compute those digits. Readers could be left with the feeling that somehow you can get information for free, which is not the case. 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. It's not just incomputability but the resources involved. I'm only barely familiar with Kolmogorov complexity and, as you point out, it looks like this is what Algorithmic Information theory is designed for but even in those scenarios, there's clearly a push and pull between run time and memory. As a heuristic, I tend to think of there being a sort of conservation law at work where sacrificing space will increase run-time and vice-versa.

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 ago
  If 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.
ttctciyf 4y ago
Yes, this is a purely theoretical observation, and not relevant to any practical compression scheme. In "algorithmic complexity" the time taken to run a program is not taken into account. There is another interesting complexity measure, Levin complexity, which does take time into account. See http://www.scholarpedia.org/article/Universal_search#Levin_complexity http://www.scholarpedia.org/article/Universal_search#Levin_c... . Regarding "information for free", I think your thought about the program that prints all strings is absolutely correct - to count as an encoding of a string the program must print just that string and then halt. What is uncomputable (in the general case) is the length of the shortest program that will encode a given string in that sense, IOW the "Kolmogorov complexity" of a string is uncomputable. See [1] for a proof of this. Roughly: Imagine a function K that computes Kolmogorov complexity, suppose the function occupies l bytes. Then consider a simple program P using this function which evaluates all strings until it finds a string s with complexity equal to l plus 10000000, then prints s and halts. Then P would have length less than l + 10000000 (because it is a tiny loop wrapped around K). But then the Kolmogorov complexity of s is equal to the length of P, because P simply prints s and halts, and P is shorter than (l + 10000000) - a contradiction. So there can be no computable function K. 1: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Formal_proof_of_uncomputability_of_K https://en.wikipedia.org/wiki/Kolmogorov_complexity#Formal_p...
- abetusk 4y ago
  My apologies, I mangled the delivery of what I was trying to say. I was trying to highlight the concerns about incomputability as the concern is real. Finding "the smallest program" of anything is, in general, for a wide a way of problems is either flat out NP-Complete, and so intractable, or just uncomputable. But we do have programs that can encode things efficiently and often we don't need the most efficient program, we can get away with some program that gets close to the theoretical limit. For example, maybe the spigot algorithm for computing the digits of pi is an example. My point was that even if you sidestep the incomputability for a moment, you're still not getting anything for free when you move to encoding things in programs. What was laid out in memory is now exchanged for run-time performance. I'm well aware of all the tricks that can be played to prove things incomputable. In my view these are variations on the proof that the halting problem doesn't exist. The more practical issue, in my view, is that NP-Complete problems are, essentially, a finite restatement of the halting problem. Instead of asking for the shortest program, ask what the shortest program is for a given finite memory and/or time bound. Then the problem does become computable, just intractable, and this is what NP-Complete problems are trying to address. For this discussion, one could imagine setting up an NP-Complete problem where the solution is the encoded video. This might be efficient to describe as a program but searching the space could blow up, costing exponential time to find.

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 ago
If 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.

ttctciyf 4y ago

Yes, this is a purely theoretical observation, and not relevant to any practical compression scheme. In "algorithmic complexity" the time taken to run a program is not taken into account. There is another interesting complexity measure, Levin complexity, which does take time into account. See http://www.scholarpedia.org/article/Universal_search#Levin_complexity http://www.scholarpedia.org/article/Universal_search#Levin_c... . Regarding "information for free", I think your thought about the program that prints all strings is absolutely correct - to count as an encoding of a string the program must print just that string and then halt. What is uncomputable (in the general case) is the length of the shortest program that will encode a given string in that sense, IOW the "Kolmogorov complexity" of a string is uncomputable. See [1] for a proof of this. Roughly: Imagine a function K that computes Kolmogorov complexity, suppose the function occupies l bytes. Then consider a simple program P using this function which evaluates all strings until it finds a string s with complexity equal to l plus 10000000, then prints s and halts. Then P would have length less than l + 10000000 (because it is a tiny loop wrapped around K). But then the Kolmogorov complexity of s is equal to the length of P, because P simply prints s and halts, and P is shorter than (l + 10000000) - a contradiction. So there can be no computable function K. 1: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Formal_proof_of_uncomputability_of_K https://en.wikipedia.org/wiki/Kolmogorov_complexity#Formal_p...

abetusk 4y ago
My apologies, I mangled the delivery of what I was trying to say. I was trying to highlight the concerns about incomputability as the concern is real. Finding "the smallest program" of anything is, in general, for a wide a way of problems is either flat out NP-Complete, and so intractable, or just uncomputable. But we do have programs that can encode things efficiently and often we don't need the most efficient program, we can get away with some program that gets close to the theoretical limit. For example, maybe the spigot algorithm for computing the digits of pi is an example. My point was that even if you sidestep the incomputability for a moment, you're still not getting anything for free when you move to encoding things in programs. What was laid out in memory is now exchanged for run-time performance. I'm well aware of all the tricks that can be played to prove things incomputable. In my view these are variations on the proof that the halting problem doesn't exist. The more practical issue, in my view, is that NP-Complete problems are, essentially, a finite restatement of the halting problem. Instead of asking for the shortest program, ask what the shortest program is for a given finite memory and/or time bound. Then the problem does become computable, just intractable, and this is what NP-Complete problems are trying to address. For this discussion, one could imagine setting up an NP-Complete problem where the solution is the encoded video. This might be efficient to describe as a program but searching the space could blow up, costing exponential time to find.