Biomedical Engineering Reference
In-Depth Information
number of computational steps the minimal program for
x
must execute. For
incompressible data, the minimal program is
print
(
x
), so
L
(
x
) |
x
|. For peri-
odic data, the minimal program cycles over printing out one period over and
over, so
L
(
x
) |
x
| again. For some compressible data, however, the minimal
program must do nontrivial computations, which are time-consuming. Thus, to
produce the second quadrillion digits of Q, the minimal program is one that
cal-
culates
the digits, and this takes considerably more time than reading them out
of a list. Thus, Q is deep, while random or periodic data are shallow.
While logical depth is a clever and appealing idea, it suffers from a number
of drawbacks. First, real data are not, so far as we know, actually produced by
running their minimal programs,
24
and the run-time of that program has no
known
physical
significance, and that's not for lack of attempts to find one
(182). Second, and perhaps more decisively, there is still no procedure for find-
ing the minimal program.
8.2.2.
Algorithmic Statistics
Perhaps the most important modification of the Kolmogorov complexity is
that proposed by Gács, Tromp and Vitanyi (183), under the label of "algorithmic
statistics." Observe that, when speaking of the minimal program for
x
, I said
nothing about the inputs to the program; these are to be built in to the code. It is
this which accounts for the length of the programs needed to generate random
sequences: almost all of the length of
print
(
x
) comes from
x
, not
print
().
This suggests splitting the minimal program into two components, a "model"
part, the program properly speaking, and a "data" part, the inputs to the program.
We want to put all the regularities in
x
into the model, and all the arbitrary, noisy
parts of
x
into the inputs. Just as in probability theory a "statistic" is a function of
the data that summarizes the information they convey, Gács et al. regard the
model part of the program as an
algorithmic statistic
, summarizing its regulari-
ties. To avoid the trivial regularity of
print
() when possible, they define a no-
tion of a
sufficient
algorithmic statistic, based on the idea that
x
should be in
some sense a typical output of the model (see their paper for details). They then
define the complexity of
x
, or, as they prefer to call it, the
sophistication
, as the
length of the shortest sufficient algorithmic statistic.
Like logical depth, sophistication is supposed to discount the purely random
part of algorithmic complexity. Unlike logical depth, it stays within the confines
of description in doing so; programs, here, are just a particular, mathematically
tractable, kind of description. Unfortunately, the sophistication is still uncom-
putable, so there is no real way of applying algorithmic statistics.
