Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!rpi!sigma
From: sigma@sun.ipl.rpi.edu (Kevin Martin)
Newsgroups: comp.compression
Subject: Re: Number theory compression ?
Message-ID: <1=dgv8b@rpi.edu>
Date: 10 Apr 91 19:14:47 GMT
References: <1991Apr7.020617.12261@nntp-server.caltech.edu> <5351@ns-mx.uiowa.edu> <4931@pink1.UUCP> <18619@csli.Stanford.EDU>
Lines: 27
Nntp-Posting-Host: ipl.rpi.edu

gandalf@csli.Stanford.EDU (Juergen Wagner) writes:
>It remains to be shown that for a particular irrational number x, any
>positive integer n, and any sequence of digits of length n, there is a
>substring of the decimal representation of x which matches that sequence.
>Before trying a compression algorithm of the described kind, we should
>guarantee that the process of looking for the substring really terminates.

Which is exactly the catch.  The process would NOT terminate unless you put
in some sort of cutoff where the program gives up and goes to a different
algorithm.  The decimal representation of x has an infinite number of
digits.  You're searching an infinite space for a given string, so it
doesn't seem you could be guaranteed to find it.

Now, if x were an irrational number consisting of the "incompressible"
string 0123456789101112131415161718192021... in its decimal representation,
all strings are in fact represented in the infinite expansion.  However,
the numbers indicating where in the sequence to find the string you want
would be at least as large as the original string!  For example, the string
'77' occurs at position '135'.  Actually, a string such as '71' occurs at
position '26' but that doesn't provide very impressive compression
considering the other possible results.

No, none of the above is rigorous.  You get what you pay for.

-- 
Kevin Martin
sigma@ipl.rpi.edu