4 ms·

Yes, this is a purely theoretical observation, and not relevant to any practical compression scheme. In "algorithmic complexity" the time taken to run a progra

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.
- ttctciyf 4y ago
  Well, yes, you're replying to me as though I was suggesting some scheme for actually compressing things. But as I say it's just a theoretical observation, nitpicking the bold claim that statistical compression techniques determine "the absolute most the movie can be compressed before you start to lose information". If the movie consisted of digital noise which turned out to be a representation of the first 10 billion digits of PI (for example) then that claim would be incorrect.

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.

ttctciyf 4y ago
Well, yes, you're replying to me as though I was suggesting some scheme for actually compressing things. But as I say it's just a theoretical observation, nitpicking the bold claim that statistical compression techniques determine "the absolute most the movie can be compressed before you start to lose information". If the movie consisted of digital noise which turned out to be a representation of the first 10 billion digits of PI (for example) then that claim would be incorrect.