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

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.