single string) is a member of a very small ensemble of relevantly similar strings. There is very little (if anything) in Shakespeare that is well-captured by the uniform ensemble; the information, to a very large degree, is specialized, regular, and non-incidental.
In other words, the effective complexity of a string is the algorithmic information content of the ensemble that “best represents” the string. If the ensemble is easy to produce (as in the case of both a random string and an entirely uniform string), then any string belonging to that ensemble is itself is low in effective complexity. If the ensemble is difficult (that is, requires a lengthy program) to produce, then any string that is a member of that ensemble is high in effective complexity. This resolves the central criticism of the algorithmic information content (i.e. Shannon) approach to defining complexity, and seems to accord better with our intuitions about what should and should not count as complex.
What, then, is the relationship between effective complexity and dynamical complexity? Moreover, if effective complexity is the right way to formalize the intuitions behind complexity, why is this the case? What’s the physical root of this formalism? To answer these questions, let’s look at one of the very few papers yet written that offers a concrete criticism of effective complexity itself. McAllister (2003) criticizes Gell-Mann’s formulation on the grounds that, when given a physical interpretation, effective complexity is troublingly observer-relative. This is a massively important point (and McAllister is entirely correct), so it is worth quoting him at length here:
The concept of effective complexity has a flaw, however: the effective complexity of a given string is not uniquely defined. This flaw manifests itself in two ways. For strings that admit a physical interpretation, such as empirical data sets in science, the effective complexity of a string takes different values depending on the cognitive and practical interests of investigators. For strings regarded as purely formal constructs, lacking a physical interpretation, the effective complexity of a given string is arbitrary. The flaw derives from the fact that any given string displays multiple patterns, each of which has a different algorithmic complexity and each of which can, in a suitable context, count as the regularity of the string.
96
