at
http://www.usyd.edu.au/su/hps/newevents/Auyang1.html
I found Sunny Y. Auyang's work, from which I excerpted:
4. Formal Definitions of Complexity and the Combinatorial
Explosion
There is no precise definition of complexity and degree of
complexity in the natural sciences. I use "complex" and "complexity"
intuitively to describe self-organized systems that have many components and
many characteristic aspects, exhibit many structures in various scales,
undergo many processes in various rates, and have the capabilities to change
abruptly and adapt to external environments. Nevertheless, there are two
definitions of complexity in the information and computation sciences that can
help us to appreciate nonreductive strategy for studying complex systems.
The idea of complexity can be quantified in terms of
information, understood as the specification of one case among a set of
possibilities. The basic unit of information is the bit. One bit of
information specifies the choice between two equally probable alternatives,
for instance whether a pixel is black or white. Now consider binary sequences
in which each digit has only two possibilities, 0 or 1. A sequence with n
digits carries n bits of information. The information-content
complexity of a specific sequence is measured in terms of the length in bits
of the smallest program capable of specifying it completely to a computer. If
the program can say of a n-digit sequence, "1, n times" or
"0011, n/4 times," then the bits it requires are
much less than n if n is large. Such sequences with regular
patterns have low complexity, for their information contents can be compressed
into the short programs that specify them. Maximum complexity occurs in
sequences that are random or without patterns whatsoever. To specify a random
sequence, the computer program must repeat the sequence, so that it requires
the same amount of information as the sequence itself carries. The
impossibility to squeeze the information content of a sequence into a more
compact form manifests the sequence's high complexity.
The information content complexity belongs to the definite
description of a specific system, thus it is not useful in science because
science is usually not so much interested in specific systems than in classes
of system that satisfy certain general criteria. It often happens that totally
random systems, which have highest information content complexity, exhibit
other types of regularity than can be characterized rather simply if we are
willing to adopt some other criteria of classification, e.g., use the law of
large numbers. We have the probability calculus for such systems, and usually
systems susceptible to the calculus are regarded as not that complex. Here we
have the first instance of the theme of this talk; the flexibility to choose
different criteria is paramount in scientific research.
The second definition of complexity describes not systems but
problems. Suppose we have formulated a problem in a way that can be solved by
algorithms or step-by-step procedures executable by computers, and now want to
find the most efficient algorithm to solve it. We classify problems according
to their "size"; if a problem has n parameters, then the size of the problem
is proportional to n. We classify algorithms according to their
computation time which, given a computer, translates into the number of steps
an algorithm requires to find the worse-case solution to a problem with a
particular size. The computation-time complexity of a problem is expressed by
how the computation time of its most efficient algorithm varies with its size.
Two rough degrees of complexity are distinguished: tractable and intractable.
A problem is tractable if it has polynomial-time algorithms, whose computation
times vary as the problem size raised to some power, for instance
n2 for a size-n problem. It is intractable if it has
only exponential- time algorithms, whose computation times vary exponentially
with the problem size, for instance 2n. Exponential-time
problems are deemed intractable because for sizable n, the amount of
computation time they require exceeds any practical limit.
And then, of course, there's Femke
Reitsma, the writer of the masters thesis which had the
offending mis-characterizations of my father's work. Aside from the fact that
Femke didn't do the proper homework-- by going to original sources for quotes
rather than relying on second-hand interpretation-- I thought the musings on
complexity contained in what I read were going in the right
direction. By "right", naturally I mean the same direction that my father had
already gone in! (I'm sure that comes as no surprise to anybody?) The
definition of a complex system here was "a whole that cannot be fully
delineated through an analysis of its component parts".
It is encouraging to see so many unrelated voices
saying that reductionism cannot help us understand complexity, but each of
these voices is talking about a mere piece of the larger framework that my
father already developed. It's a shame to have so many people re-inventing the
wheel when their time could be better spent using it to travel where my father
never got to.
Judith