You give lossless compressors too little credit. An optimal text compressor (with a sane running time) should be able to "understand" the context to generate a

You give lossless compressors too little credit. An optimal text compressor (with a sane running time) should be able to "understand" the context to generate a density function over words close to the true one to encode optimally. The lossy one if optimal in some manner should generate this same density but it would use an error metric to achieve a "rate-distortion" boundary, and encode optimally based on the desired position on that boundary. So what separates the two is the error metric, in other words, how much humans would bother if you replaced y for x. But this involves humans, not general intelligence -- you'd need a lot of testing with actual humans to get good results (jpeg has extensive testing to find optimal quantizers for chroma values based on human perception, for example). Not that the latter would not be interesting too; I just think it's less practical. Relevant: http://www.stanford.edu/class/ee368b/Handouts/04-RateDistortionTheory.pdf http://www.stanford.edu/class/ee368b/Handouts/04-RateDistort...