From: kv07@IASTATE.EDU (Warren Vonroeschlaub)
Subject: Re: CWACKers and Complexity (bits of information definition)
Reply-To: kv07@IASTATE.EDU (Warren Vonroeschlaub)
Organization: Ministry of Silly Walks
Date: Wed, 11 Nov 1992 23:44:17 GMT

In article <9iF2TB1w165w@kalki33>, kalki33!system@lakes.trenton.sc.us writes:
> kv07@IASTATE.EDU (Warren Vonroeschlaub) writes:
> > In article <7F9VTB1w165w@kalki33>, kalki33!system@lakes.trenton.sc.us
writes:
> > > If we confine the discussion to actually existing books, eliminating the
> > > nonsense ones and the ones which were never printed, then it is possible
> > > to compress the descriptions with suitable coding (i.e. Huffman). But
> > > this introduces an algorithm whose information content must also be
> > > taken into account. In addition, we would have to supply all the text of
> > > all the existing books to the coding process!
> > 
> >   Uh, not quite.  Are you saying that my hard disk with Stacker (which
> > compresses the data) takes up just as much space as the uncompressed data?
[discussion of compression deleted (I have studied it and knew all the stuff)]

> For example, if you want to ZIP a file, you must have the ZIP program
> itself stored somewhere. This is extra information. Also, the ZIP
> program must process each character in the file to be compressed, so
> that the original file must be stored somewhere too. The final outcome
> may be a smaller file, but the total process actually involves more
> information than was in the original file.

  El wrongo!  Provided the data can be compressed, the information contained
inside is the _compressed_ value, not the uncompressed+compression algorithm +
compressed.  The string 11111111111111..... contains the information "rep(1)" (a
nice short Turing machine).  There is no need to take the original infinite
string of 1s into account.

> I was using the example of Huffman coding because, in principle at
> least, it can give the greatest possible compression ratio. I believe
> that my analysis was correct.

  Not if we are doing universal Turing machines.

>>   Also (and I am not 100% sure of this, so any experts correct me if I have
t
>> confused with another aspect of information theory) the actual data isn't
wha
>> is supposed to be used anyway.  The information content is supposed to be
bas
>> on the size of the smallest universal Turing machine that can generate the
da
>> Taking advantage of proprietary compression schemes is assumed, not
excluded.
> 
> Yes, that is true. However, in the case of a data source that is
> "random", (and the set of all possible books will exhibit statistical
> randomness, since every letter and every combination of letters will
> occur with equal frequency), the shortest Turing machine program will be
> exactly the one which simply copies the data to its tape, letter by
> letter. To do this, the data will have to be on the tape (or somewhere)
> already, and will thus be part of the program!

  Are you suggesting that a cell is random?  My DNA does a fairly good job at
representing most of my appearance (and even some of my past appearance) in a
tiny amount of space.  The process for extracting this information is the "low
information content" physical laws.  Thus, I am of low information content.

> There may be some argument here from Turing machine specialists, since a
> distinction can be made between the "program" and the "data". However,
> it must be admitted that the total information needed by the Turing
> machine includes not only its string of instructions but also the string
> of data on which it operates.

  Turing machines don't have data.  (Except of course the information written
out earlier)  All it has is the compressed data in terms of instructions.

  I guess you could think of this as saying that the amount of information is
proportional to the smallest ZIP2EXE file generated by any compression routine
(to be run on the UTM 1.0 platform).

> I think the difficulty of understanding may lie in realizing the
> distinction I made between the two sets of books. I understood "all
> possible books" to mean all possible strings of characters of a given
> length (the number of characters in a typical "book") drawn from a fixed
> alphabet of 64 characters (covering upper/lower case, numerals and some
> punctuation). This of course includes immense numbers of "jibberish"
> books, as well as some "meaningful" books that have not yet been --or
> never will be-- written.
> 
> Randomly distributed --or uniform-- information may not be compressed
> any further, whereas nonuniform information certainly can.

  So a random glob of primordal chemicals has much higher information content
that a similar sized, but highly ordered, cell.  It seems you have disproved Dr.
Thompsons thesis.

> Of course, I too welcome the comments of professional information
> theorists!

  Sorry, only a hobbyist.

 |  __L__
-|-  ___  Warren Kurt vonRoeschlaub
 |  | o | kv07@iastate.edu
 |/ `---' Iowa State University
/|   ___  Math Department
 |  |___| 400 Carver Hall
 |  |___| Ames, IA  50011
 J  _____