Occasionally one compression algorithm will compress information A to be
smaller than B, and another making b smaller than A, so it's tricky to use
practical compressibility even for comparisons, in some cases.
Also, it -is- easy to come up with an algorithm that compresses the
Britannica -- and only the Britannica -- down to a 1 bit file. (In my
example, everything but the EB is compressed via PKZIP [a ubiquitous
PC-based compression program].)
The problem, as Yockey would point out, is that my compression/decompression
algorithm simply contains the entire EB within it (to recognize it during
compression, and to insert it during decompression of the unique 1-bit
file), and so is presumably larger than the -normally- compressed EB itself,
and so (by agreement) doesn't count as a success.
But then I wonder -- if information is compressible IFF a smaller program
can generate it, then are small quantities of information uncompressible per
se? E.g., "111111" seems pretty compressible, but I bet it'd be hard to
write a 5-instruction program (especially using Turing machine instructions)
to generate it.
Also, who gets to specify which program instructions are available
But this is a tangent. I'll agree to say no more if you do. :^>
--John
> -----Original Message-----
> From: Glenn Morton [mailto:grmorton@waymark.net]
> Sent: Monday, December 29, 1997 3:29 PM
> To: John E. Rylander; Calvin Evolution Reflector
> Subject: RE: ABCDEFGHIJKMNOPQRSTUVWXYZ
>
>
> At 05:45 AM 12/29/97 -0600, John E. Rylander wrote:
> >
> >Glenn,
> >
> >Just a minor question: this degree of compressibility will vary
> >significantly with the algorithm used to compress, no?
> >
>
> This is true. Various compression algorithms will compress something more
> than another. All one can say with compressibility is that given 2
sequences
> one sequence has more information than the other because it is less
> compressible. The maximum known compressibility is what can be used to
> relatively quantify information. In other words, one can not use
> compressibility as a measure of the absolute quantity of information only
> for a comparison. One cannot prove that he has the shortest possible
> compression of a sequence. If you could do that, you could prove that a
> given sequence is random. But as it is, we can't. Yockey states:
>
> "The considerations in section 2.4.1 might lead us to believe that, having
a
> definition and a measure of randomness, one could prove a given sequence
to be
> random. In fact it is impossible to do so. It can easily be shown that a
> given sequence is not random. We need only find a program that compresses
the
> sequence to one substantially shorter than the sequence itself. We need
not
> prove that the program is the shortest one, just that is is shorter than
the
> original sequence. On the other hand to prove that a given sequence is
indeed
> random one must prove that no shorter program exists. This leads
immediately
> to the paradoxes of sets that have themselves as members. Epimenides, the
> Cretan, alleged, 'All Cretans are liars'. Is that statement true or fals?
> Consider the Berry paradox: 'Find the smallest positive integer that to
be
> specified requires more characters than there are in this sentence.' The
> sentence supposedly specifies a positive integer of more characters than
there
> are in the sentence. We are now in the midst of a subtle and fundamental
> anomaly in the foundations of mathematics, discovered by Chaitin that is
> related to a famous theorem due to Kurt Godel called Godel's
incompleteness
> theorem. Godel showed that for the axioms defining number theory there
are
> always theorems that can neither be proven or disproven from the set of
> axioms. This theorem caused considerable Angst among mathematicians
> comparable to that among physicists caused by quantum theory and
relativity
> theory."~Hubert Yockey, Information Theory and Molecular Systems,
(Cambridge:
> Cambridge University Press, 1992), p. 80-81
>
>
> >And for any particular information, it's possible to make a (custom-made)
> >compression engine that will reduce it to 1 bit, right?
>
> Absolutely not. In compressing a sequence you must be able to uncompress
it
> or you have lost information. Take this post and let us use your patented
> 1-bit compression algorithm. This note compresses to "1". But the
> Encylopedia Brit. also compresses to a "1". Thus you have the
contradictory
> situation that this post has as much information as the Encyclopedia
> Britannica. I know it has as much wisdom. :-)
>
>
> glenn
>
> Adam, Apes, and Anthropology: Finding the Soul of Fossil Man
>
> and
>
> Foundation, Fall and Flood
> http://www.isource.net/~grmorton/dmd.htm
>
>