[Next] [Previous] [Top] [Contents]

Complexity and Scientific Modelling

4 Other Formulations of Complexity

There is not room to do anything but mention but a few of the other formulations of complexity here (see [4] for a reasonably complete listing). I will only look at three here (I am distinguishing here between complexity and simplicity as it is traditionally used in philosophy, for this see section 8, below).

The Algorithmic Information of a pattern can be considered as the difficulty of storage of a program to generate the pattern (or alternatively the difficulty in finding such a program when working though possible programs in order of length).

Grassberger [6] defines the Effective Measure Complexity (EMC) of a pattern as the asymptotic behaviour of the amount of information required to predict the next symbol to the level of granularity. This captures an aspect of the scaling behaviour of the information required for successful prediction by a markov process model. This thus captures the asymptotic behaviour of a special case of my definition. A similar approach is taken by Badii and Politti [1].

The topological complexity described by Crutchfield [3], is a measure of the size of the minimal computational model (typically a finite automaton of some variety) in the minimal formal language in which it has a finite model. Thus the complexity of the model is both `objectivised' by considering only minimal models but also related to the fixed hierarchy of formal languages. This has a number of disadvantages. Firstly this does not give a unique complexity for any pattern, as there is not necessarily such a "minimal" formal language, secondly in some formal languages the minimal model is uncomputable and thirdly in stochastic languages the minimal model will frequently be a completely random one, so one is forced to trade specificity with complexity to get a reasonable result. He also defines a measure of specificity similar to EMC above, as complementary to the topological complexity.

In each case the desire to attribute complexity purely objectively to a physical process seems to force a relativisation to either some framework for which privilege is claimed (e.g. a Turing Machine), to some aspect of the problem (e.g. granularity of representation) or by considering only the minimal size. This, of course, does not completely eliminate the inherent subjective effects in the process of modelling (principally the language of modelling), and obscures the interplay of complexity, specificity and the error involved.

Complexity and Scientific Modelling - 04 APR 97

[Next] [Previous] [Top] [Contents]

Generated with CERN WebMaker