From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: Re: The Dualism in info theory
Date: 13 Oct 92 16:24:52 MDT
Organization: University of Utah, CompSci Dept

>Take the program, P1, to perform quick-sort on N numbers,
>written for assembler language, or rather instruction-set, S1.
>It consists of M1 bits of op-codes+data.
>
>Take the program, P2, to perform quick-sort on N numbers,
>written for assembler language, or rather instruction-set, S2.
>It consists of M2 bits of op-codes+data.

There are two interesting questions (at least) embedded in this scheme:

1) If we are achieving the same end, and we have two different ways
to achieve that end, does one way contain more information than the other?
I cannot answer this directly, for I do not know.  However, one could
certainly have many different possibilities:  One could be longer in
instructions, and one could be longer in running time.  I would answer
off the cuff by saying: the amount of information in an algorithm is the
shortest possible code for that algorithm, regardless of run time.

2) If we are using the exact same algorithm, but our instruction sets are
different what is the fundamental information difference?  Here, I am
more certain: both contain the same exact amount of information.  Some of
the information already is stored in one instruction set, making its code
appear shorter although it technically is not.   For instance, one set might
have the sqrt() function, and in the other we must write this explicitly.
However, once we have written it explicitly (taking up room) we could call
it over and over...... In arguments about Kolmogrov information (which using
a computer to determine information content) one Universal machine is chosen
as the measure for all other things... thus we would have to translate
the two codes into the universal machine code, and see one was longer.  
Since you suggested they were the same algorithm, then they would be
necessarily identitlce.  Note that the universal machine is chosen precisely
to ELIMINATE the problem you suggested... But it is still a VERY INTERESTING
problem (more on that in a second)

>This, to me, seems very much like Tom's question, how much information do you
>need to deliver a letter, or to wander down to stores?  How much information
>needs to be on the envelope, and how much is 'encoded' by the maze (by the
>road network, or the corridor layout).

I am not sure about this.... how much coding do we need given some implicit
information, is that the idea here?  For instance, there is lots of implicit
information in delivering a letter for the postman... that he can look at
a map, or else has an internal model of the area, that he can read the
numbers on the houses and match them and extrapolate... and so forth. Not an
easy problem, you will well know, if you have ever subbed on a paper route!

Let me get back to your question about instruction sets... there is a really
clever and interesting thing going on in the background here.  Lets suppose
we chose some machine with the SQR(), SIN(), and COS() functions.  Clearly,
it would have a smaller instruction set for certain computations.  In fact,
we could design the code so that these instructions had a minimal size, they
were all 1 or 2 bits long.  Some scientific code would be greatly reduced
using this instruction set.  However, we might have some other code which
did NOT use these functions, and as a result it would be correspondingly 
longer, for it would alway use the longer codes!  Quite a puzzle.

Lets go even further, and postulate more "advanced" machines.  We will let
the machine have a code for ANY function whatsoever.  What would be the
ideal set of codes for that machine?  Clearly, it would depend on what
computation we were running.  In fact, if we knew the computation in advance,
we could set the code of 1 to be equal to that very computation (because
every computation is a function).  Thus, our instruction set would be of
length 1, very short indeed.

However, in general we do not know our computation in advance, so we would
have to make do with our "advanced" machine making short codes for expected
functions. (sounds a lot like shannon now, somehow)  This also sounds a lot
like some of AI theory... group a task into subtasks, and the already solved
subtasks can be relatively ignored.  

Anyway, according to Kolmogrov definition, the same program on different
systems contains the same amount of information (because we translate the
two into the universal code).  A system could save a specific program a lot
of work be already having "primitives" which solve some of its goals, but
these same primitives could also be encumbering (as mentioned above)  We
could speculate wildly about now, and suggest: the human brain can only keep
in its head an algorithm of limited complexity.  Thus, in order to make
progress, specific functions (or methods or ideas) need to be chunked into
smaller codes (primitives).  Mental breakthroughs occur by rearranging these
chunks, or by "rechunking" the language to allow for novel synthesis.

If you repost your H idea, I will tear it up (or praise it wildly, depending)




Newsgroups: bionet.info-theory