Biomedical Engineering Reference
In-Depth Information
This observation goes the other way: complex data look random. The heu-
ristic idea is that if there were any regularities in the data, we could use them to
shave at least a little bit off the length of the minimal program. What one can
show formally is that incompressible sequences have
all
the properties of IID
sequences—they obey the law of large numbers and the central limit theorem,
pass all statistical tests for randomness, etc. In fact, this possibility, of defining
"random" as "incompressible," is what originally motivated Kolmogorov's work
(107, ch. 3).
Kolmogorov complexity is thus a very important notion for the foundations
of probability theory, and it has extensive applications in theoretical computer
science (177) and even some aspects of statistical physics (178). Unfortunately,
it is quite useless as a measure of the complexity of natural systems. This is so
for two reasons. First, as we have just seen, it is maximized by
independent
ran-
dom variables; we want
strong dependence
. Second, and perhaps more funda-
mental, it is simply not possible to calculate Kolmogorov complexity. For deep
reasons related to Gödel's Theorem, there cannot be any procedure for calculat-
ing
K
(
x
), nor are there any accurate approximation procedures (177).
Many scientists are strangely in denial about the Kolmogorov complexity,
in that they think they can calculate it. Apparently unaware of the mathematical
results, but aware of the relationship between Kolmogorov complexity and data
compression, they reason that file compression utilities should provide an esti-
mate of the algorithmic information content. Thus one finds many papers which
might be titled
gzip
as a measure of complexity,"
23
and the practice is even
recommended by some otherwise-reliable sources (e.g., (73)). However, this is
simply a confused idea, with absolutely nothing to be said in its defense.
8.2. Refinements of Algorithmic Complexity
We saw just now that algorithmic information is really a measure of ran-
domness, and that it is maximized by collections of independent random vari-
ables. Since complex systems have many strongly dependent variables, it
follows that the Kolmogorov notion is not the one we really want to measure. It
has long been recognized that we really want something which is small both for
systems which are strongly ordered (i.e., have only a small range of allowable
behavior) and for those which are strongly disordered (i.e., have independent
parts). Many ways of modifying the algorithmic information to achieve this have
been proposed; two of them are especially noteworthy.
8.2.1.
Logical Depth
Bennett (179-181) proposed the notion of the
logical depth
of data as a
measure of its complexity. Roughly speaking, the logical depth
L
(
x
) of
x
is the
