question on algorithmic complexity

Bill Hamilton (hamilton@predator.cs.gmr.com)
Wed, 17 Jan 1996 16:22:46 -0500

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? As I said earlier, one of
the things human designers strive for is elegance, which might be defined
as achieving simplicity in design. A truly elegant design might, if it can
be expressed in terms of algorithmic complexity, might be quite a bit less
complex than a poor, patched up design.

BTW, I could use a pointer to relevant works by Chaitin. I think he had a
book from MIT Press that I wanted to take a look at a while ago, but all I
found in the GMR library was the following:

AUTHOR: Chaitin, Gregory J.
TITLE: Information-theoretic incompleteness.
IMPRINT: Singapore ; River Edge, NJ : World Scientific Pub. Co., c1992.
COLLATION: viii, 226 p.
SERIES: World Scientific series in Computer Science ; vol. 35
SUBJ: Machine theory.
Computational complexity.
CALLNUM: QA267 .C5

Bill Hamilton | Vehicle Systems Research
GM R&D Center | Warren, MI 48090-9055
810 986 1474 (voice) | 810 986 3003 (FAX)
hamilton@gmr.com (office) | whamilto@mich.com (home)