Xref: utzoo comp.compression:59 alt.comp.compression:176
Newsgroups: comp.compression,alt.comp.compression
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!sarah!bingnews!kym
From: kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell)
Subject: Re: theoretical compression factor
Message-ID: <1991Mar26.051851.23533@bingvaxu.cc.binghamton.edu>
Organization: State University of New York at Binghamton
References: <1991Mar25.031214.25696@bingvaxu.cc.binghamton.edu> <1991Mar25.054838.15588@bingvaxu.cc.binghamton.edu> <15098:Mar2512:53:1291@kramden.acf.nyu.edu>
Date: Tue, 26 Mar 1991 05:18:51 GMT

In <1991Mar25.031214.25696@bingvaxu.cc.binghamton.edu> I wrote:
>Some strings have `low complexity' in the sense of Martin-Lo{f.
^^^^^^^^^^^^^
>(The program that can type them out is much shorter than the
>actual string).
>For such strings it is obviously better to store or transmit the _program_ 
     ^^^^^^^^^^^^
>than the string. Some method needs to be found to enumerate the possible 
>programs useful for this purpose.

In <15098:Mar2512:53:1291@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) wrote:
>There is no way that a compressor can turn every string with as many 0's
					    ^^^^^
>as 1's into a string of half the length.

In case I've misrepresented myself as Dan perhaps thinks, I've included some 
introductory text from my original message.

Dan's point is of course correct -- there are certain bitstrings whose 
complexity prohibits any program from being written that is in any
sense `shorter' than the given bitstring. Essentially the only programs that
can reproduce such bitstrings are:

	PRINT ``SEQUENCE-OF-BITS''

However, by the definition of certain mathematicians, such bitsrings would be 
regarded as essentially ``random'' (see, e.g., Knuth v2 who is/was _not_ one 
of these) and I _think_ the number of text files, with which I am primarily
concerned, that exhibit such a property are vanishingly small;
text files on a computer are USUALLY generated by programs shorter than they 
are!

-kym