Re: Fixpoint for LZH

From: *** T. Winter (***.Winter_at_cwi.nl)
Date: 07/19/04 

Date: Mon, 19 Jul 2004 01:14:49 GMT

In article <1090049632.322988@athnrd02.forthnet.gr> morpheus@olympus.mons writes:
> *** T. Winter wrote:
> [snip]
> > > I stand corrected. I was rather using "strict contraction" in the sense
> > > of the previous article, but your and David's points still stand, even
> > > under this definition: size(f(file))> size(file) =/=> f does not have
> > > any fixed points.
> >
> > But you have not actually shown that size(f(file)) never equals size(file).
>
> Even if f is such that size(f(file))=size(file), this says nothing about
> the existence of a fixed point of f.

Yup, exactly what I said below.

> > With all kinds of schemes that may change filesize, and in some cases leave
> > it unchanged, it is possible that a fixed point does exist.
>
> It is possible that several schemes may have a fixed point, but it
> appears to me as though a filesize change doesn't imply anything about
> the existence of said point.

Where do I say that there is an implication? I only say that it is
possible that such does exist!

> In that sense, zip appears to be fundamentally different from Stuffit
> for example, in that Stuffit for Macs if memory serves right, never
> increased file size. It's been a while since I was using a Mac, so my
> memory may be failing me on this.

Stuffit will never increase filesize indeed. But that is a program that
uses quite a few different compression formats and if any of them fail
to make the file shorter, it will just produce the original. The point
was *not* whether a particular program has a fixed point (I know some
for Stuffit), but whether a compression scheme has a fixed point. 

-- 
*** t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~***/
Quantcast