Re: question on algorithmic complexity

Eddie G. Olmstead, Jr. (olmstead@gordonc.edu)
Fri, 19 Jan 1996 10:35:53 -0500

Brian Harper:
>>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.

Bill:
>Well, I'm not advocating that it be tossed out. I'm only suggesting that
>additional criteria need to be brought to bear, because I believe putting
>on blinders and using AC alone as a measure of complexity could lead to
>absurd results.

I agree with Bill that randomness alone is not a measure of complexity.
However, I think I know where Brian is going. A simple sequence of
"HTHTHTH..." is not complex because you could write one simple algorithm to
generate it. The order is very simple--like a NaCl crystal with an endless
repeation of a simple pattern. There is order, but very little information.
However, to generate the sentence "DNA is a complex molecule", it takes a
much larger (but still finite) set of algorithms--rules of spelling,
grammer, etc. of the English language. The order is much more complex, but
it contains information precisely because isn't simple repition--like a DNA
strand. A totally random sequence doesn't obey any rules. Thus, it is
complex and disordered. Thus, we are looking for "ordered complexity" if
you will. I'm eager to find out if I guessed correctly, but I'm willing to
let Brian write up his full post that he has been promising us so he can
define the terms more carefully than I've used.
__________________________________________________________
"Looking back, there's a thread of love and grace
Connecting each line and space I've known" -David Meece
==========================================================
Eddie Gene Olmstead, Jr. Chemistry Department
Asst. Professor of Chemistry Gordon College
Email: olmstead@gordonc.edu 255 Grapevine Road
Phone: (508) 927-2300 Ext. 4393 Wenham, MA 01984