>This question is for Brian Harper, but it may be of interest to others.
>You have suggested that there is a connection between algorithmic
>complexity and design, and that raises a question in my mind. I am
>presuming that one possible definition of algorithmic complexity might be
>applied to a sequence, and the algorithmic complexity in this case might be
>some measure of the length of the algorithm required to generate it (or,
>more properly, maybe we should say the minimum length algorithm which will
>generate it, but I suppose that problem might be NP hard). In any case, if
>that definition is suitable, what would be the algorithmic complexity of a
>pure random sequence (not psueudorandom, but truly random?) Might it not
>be very large, or even infinite? If so, and if my earlier assumptions are
>reasonable, shouldn't we be willing to consider that the algorithmic
>complexity definition of design is incomplete?
In retrospect I should have said more about the point Bill is making
here than I did. Sometimes I think I should add a disclaimer to each
of my posts in the hopes that people won't mis-interpret me. I tend
sometimes to be very blunt in what I say which may lead one to
conclude that I think a particular observation is either obvious
or noncontroversial. It may also cause one to conclude that I'm
rigid and dogmatic about some things. Actually, I'm not, I change
my mind about stuff all the time, perhaps too often :-).
More to the point, my reply to Bill may have suggested that I
thought his objection to be a trivial one. In fact, it is not.
Actually, it shows that Bill's insight into this problem is
very keen. Given my glowing portrayal of algorithmic complexity,
it may surprise people to know that, even though AC was the first
precise definition of complexity, it is now under a rather dark
cloud in some circles. The reason being exactly that given by
Bill above. If you look through the different popularizations
that I mentioned you will find in most if not all a final
conclusion about AC that goes something like this:
"In spite of its various merits, AC suffers from one
serious drawback. It is really a measure of randomness
and randomness is not what we generally mean by complexity"
Its amazing really how often this or something very close to it
appears not only in popularizations but also in the primary
literature. IMHO, this is wrongheaded and confused [I think I'm
safe now :), Bill won't be offended since he is in very good
company (Murray Gell-Mann, Paul Davies, John Casti etc etc)].
First, the implication of the above statement is that randomness
is not complex, a very strange notion ;-). Also, and more importantly,
when you look at precisely "...what we generally mean by complexity"
you'll find that what they generally mean by complexity is what
I, Chaitin, Yockey and others are calling organized. So, I think
this confusion boils down to one of semantics. The sad thing is
that the best definition of complexity might get tossed out simply
on account of confusions about words.
========================
Brian Harper |
Associate Professor | "It is not certain that all is uncertain,
Applied Mechanics | to the glory of skepticism" -- Pascal
Ohio State University |
========================