🚀 go-pugleaf

In article <1992Nov18.024912.24072@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:

>>...information theory does not set an absolute limit on maximum compression 

> As I understand it, Chaitin/Kolmogorov Algorithmic Information Theory
> does set an absolute limit to the degree to which any given data can
> be compressed... subject only to the choice of a particular universal 
> Turing machine. (This last proviso would not have any effect in practice.)

When people talk about an "absolute limit on maximum compression", they
are referring to an ABSOLUTE theoretical limit on maximum compression.

Chaitin/Kolmogorov Algorithmic Information Theory does not give such
a limit, for the very reason you note - it depends on a particular 
choice of universal Turing machine. By chosing the Turing machine 
appropriately, I can make any string have any complexity whatsoever.
Saying that it's not an issue in practice is not germaine - we aren't
talking about PRACTICAL limits, but about ABSOLUTE, THEORETICAL limits.

In any case, none of this has anything to do with the original topic,
which was fractal compresion. The claims made for this technique do
indeed seem rather dubious, given their coyness about releasing hard
information, but they certainly can't be ruled out on theoretical
grounds, even allowing for some additional "practical" constraints.
There's not enough known about the psychology of human vision to tell
how much information can be deleted from images without harm, and
there's not enough known about the universe of images to say how
redundant they are.

    Radford Neal