The mathematical term you're looking for is Idempotence [1]. I'm speculating that the difficulty of such a feat depends on how many free variables an encoder h

The mathematical term you're looking for is Idempotence [1]. I'm speculating that the difficulty of such a feat depends on how many free variables an encoder has to choose from. For example, in the case of a compressor, there are probably quite a few arbitrary choices that can be made at the compressor side that make little difference to compression quality in general -- but may make reproducing the exact same result difficult. The search-space might be very large. I'll also speculate, though, that even if perfect reproduction is not possible, a compressor that's designed to work on the digital output of a decompressor of the same algorithm can probably be designed to do a better job on that particular example. [1] http://en.wikipedia.org/wiki/Idempotence http://en.wikipedia.org/wiki/Idempotence