From: mshute@cs.man.ac.uk (Malcolm Shute)
Newsgroups: bionet.info-theory
Subject: Post Office Game (again, sorry)
Date: 14 Sep 92 13:53:00 GMT
Organization: Dept Computer Science, University of Manchester, U.K.

Do you remember the following grid?  I promised to shut up about it for a while,
and did... but I've just thought of something new to suggest about it (so
please bear with me again).

   +===+===+===+===+===+===+===+===+
111|   .   :   .   |   .   :   .   |
   |.#####.:.#####.|.#####.:.#####.|
110|   #   :   #   |   #   :   #   |
   +---D###E####---+---#########---+
101| A #   #   #   |   #   #   #   |
   |.B#C##.#.#####.|.#####.#.#####.|
100|   .   #   .   |   .   #   .   |
   +===+===F#######G#######H===+===+
011|   .   #   .   #   .   #   .   |
   |.#####.#.#####.#.L#K##.#.#####.|
010|   #   #   #   # M #   #   #   |
   +---#########---#---J###I####---+
001|   #   :   #   #   #   :   #   |
   |.#####.:.#####.#.#####.:.#####.|
000|   .   :   .   #   .   :   .   |
   +===+===+===+===X===+===+===+===+
    000 001 010 011 100 101 110 111

If you remember, this was connected with my trying to read something more
into Tom's comment about "It's the post office game all over again...
how many bits of information does a postman need to deliver a letter,
or does an office worker need to walk down to get something from stores?"

The grid is supposed to represent a map of the world, with lattitude and
longitude, and a system of roads marked in.  Or, on a smaller scale, it could
be a map of an office site, with a system of corridors marked in.

What I had hoped was that this would shed some light on the question
"what is the information content of a system of roads, a system of
corridors, a decision tree in an instruction decoder in a CPU, etc?"

I first of all suggested that we compare an ICBM travelling from A to M
without using the network, with a postman travelling along the road
marked ###.  At all stages, the ICBM would need 6 bits of destination
address + 6 bits of current position.  Meanwhile, the road-travelling
postman could make do with a 13-bit shift-register, with the 12 left-right
decisions listed for points BCDEFGHIJKLM, plus a '1' and '0' stop bit.

Thus, this didn't get me forward very far.

How, then, about the following thought:

Suppose, instead of trying to get from A to M, the idea is to start from
(000,000), and to find the room which contains the hidden object (finding
a needle in a hay stack).

The corridorless method (ICBM) would involve threading a zig-zag pattern
like that used in Cantor's method: (000,000), (001,000), (000,001), (000,010),
(001,001), (010,000), etc.

On the other hand, the corridor-based method could use a maze-solving algorithm.
Now, *if* it is *given* that the maze is a tree-shaped network, as in the
diagram above, we don't need *any* bits of information.  We just put our hand
on the right-hand wall (say) and inspect each of the rooms on the way until
we find the one which contains the needle.  A more general maze would not be
so easy, and would require us to store more bits of information (either in our
mind, or by placing marks in the maze).

The ICBM is getting through information at the rate of 12 bits per square
(given that it is constantly having to compare its present position to its
intended destination, given in the sequence above).
In the worst case, the ICBM travels 63 squares to find the needle, at the
cost of 756 bits of information.

In the worst case, the walking maze-follower, though, travels 115 units of
distance.

Can I therefore conclude that the maze-less traveller (the ICBM) needs
12 bits per unit distance (ignoring the factor of sqrt(2)); whilst the
maze travel needs no information, but takes longer... consuming the
*equivalent* of 756/115 bits per unit distance *implied*by*the*structure*
of the maze itself.  (756/115=6.5739)



Talk about fuzzy-headed thinking!!  :-)

As you can see... I still don't have enough grasp of subject to get across
what I am trying to do here.
Can anyone help me out... and either show me how my argument *should* have
proceeded... OR... show me that there is nothing to be shown by this argument?
--

Malcolm SHUTE.         (The AM Mollusc:   v_@_ )        Disclaimer: all
Newsgroups: bionet.info-theory