🚀 go-pugleaf

radford@cs.toronto.edu (Radford Neal) writes:

>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.

This is a complete red herring.
All right, let us agree to take the universal machine
defined in

@book{davis73
author = " Davis, M.",
title = "Computability and unsolvability",
publisher = "Dover",
year = 1973,
isbn = 0486614719
}

Now there is no doubt about it.
(The choice is irrelevant,
because if you insisted on the definition
in Marvin Minsky, "Finite and Infinite Machines",
you would reach exactly the same conclusion.)

>In any case, none of this has anything to do with the original topic,
>which was fractal compresion.

It has everything to do with this.
It shows beyond the slightest doubt
that it is not possible to reach the kind of compression
Barnsley speaks (or spoke) of,
without loss of information (ie reversibility).

>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.

If this is meant to be in response to my posting,
I said explicitly that this compression was not possible
_without loss of information_.
If you now accept that some information is lost,
but argue that it wasn't very valuable information anyway,
you are into a completely different realm,
where I have no intention of following you.


-- 
Timothy Murphy  
e-mail: tim@maths.tcd.ie
tel: +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland