Re: Fixpoint for LZH

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

Date: Sat, 17 Jul 2004 00:54:59 GMT

In article <1089983715.777403@athnrd02.forthnet.gr> morpheus@olympus.mons writes:
> Gareth Owen wrote:
> [snip]
> > You said "LZH isn't a contraction so it doesn't have a fixed point" (which
> > would be an incorrect syllogism, even if you were using contraction in the
> > mathematical sense).
>
> 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).
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. I know of
a better example back from the 80s. If you fed some file to the C compiler,
captured the error messages, fed those back in again, and repeating, you
might (with a particular compiler) indeed get a fixed point. Examples have
been shown at that time.

Off-hand I see no reason why LZH (for some definition of the many variants)
does not have a fixed point.

Anyhow, as Phil stated there is a file that gunzips to itself. The
message-id: <40c3f78f@news.orcon.net.nz>. If that is possible, it is
very plausible that there also will be files that gzip to itself. 

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