From: mshute@cs.man.ac.uk (Malcolm Shute)
Newsgroups: bionet.info-theory
Subject: Re: More wacky theory
Date: 14 Sep 92 11:55:15 GMT
Distribution: bionet
Organization: Dept Computer Science, University of Manchester, U.K.

In article <MADAVIS.92Sep11141316@sparta.nmsu.edu> madavis@nmsu.edu (Mark Davis) writes:
>One complaint about the Chaitin/Kolmogorov measure is that it gives
>bigger numbers when the system is more random (in Chaitin's sense;
>not reducable to a simpler representation).  The intuitive notion
>about complexity is that a completely uniform material should have
>low complexity and a highly disordered material should also have
>low complexity.  It is only a tenuous intermediate that should
>receive high marks for complexity.  An approach by Hubermann and Hogg
>normalizes the measure with a measure of maximum complexity for
>a class of same-size systems, thereby providing precisely the
>desired spectrum.

I know nothing about this animal... but what you said about complexity
and randomness struck a chord.

Computer memory can be packed more densely (more transistors per unit area
of silicon) than can computer CPU logic.  The reason is that memory,
especially DRAM, is just a mindless uniform array of bits, with one
transistor per bit of storage; however, the CPU needs a register here,
a signal lead there, an AND gate over there.

I agree that the memory array, like a crystal lattice, though being big,
is extremely simple.  It's structure can be summarised by a couple of
simple algebraic expressions.

I also agree that a truely random pattern is not simple to describe
(you have to spell out where each component goes... there is no structure
to summarise algebraically)... but equally has no structure.

The paradox, or problem, or however you like to view it, then, is how
to distinguish between the CPU hardware, which has no *regular* structure
to summarise succinctly, but never-the-less has *a* structure for a purpose...
and the random noise pattern, which also has no *regular* structure, but
has no meaningful purpose for its particular pattern either.

Phrased like this, we are going to have to define complexity (and information
content, etc) in terms, not only of regularity of its structure (or lack
thereof) but also the nature of the job that it is designed to perform.

This then comes back to my comment last week, from Richard Dawkins' "The Blind
Watchmaker".  Mont Blanc is a complex structure... with millions of fragments
of intricately shaped rocks making it up.  However, much of this complexity
is random.  Mont Blanc would still do the same job if someone where to come
along and muddle up some of its rocks, or even replace some of them.  However,
a CPU would not work if you swapped a couple of its leads over, or replaced
them with something else.

As far was we know, then, the CPU is more complex (has more intentional
structure) than Mont Blanc.

However, as "Hitch Hiker's Guide to the Galaxy" fans would be quick to point
out, we're only assuming that Mont Blanc would perform the same job with its
components mixed up a bit.  How do we know that it isn't an extraterrestial's
computer, with every fragment of rock performing a specific function?

So, clearly this is a blind alley, too, as a means of defining complexity
of structure.  It would work fine for things that *we* have designed, but
not for things like Mont Blanc and the Universe... (where there is some
argument over whether they *have* a purpose, let alone *what* that purpose is).
--

Malcolm SHUTE.         (The AM Mollusc:   v_@_ )        Disclaimer: all