1. Introduction
In algorithmic information theory, the information content of a string of digits is measured by the string's algorithmic complexity. In informal terms, the algorithmic complexity of a string is defined as the length of the shortest algorithm that, when provided as input to a universal Turing machine, generates the string. A string has maximal algorithmic complexity just if the shortest algorithm able to generate it is not significantly shorter than the string itself, allowing perhaps for a fixed additive constant (Li and Vitányi Reference Li and Vitányi1997).
Any pattern or regularity in a string lowers its algorithmic complexity. This is because a pattern constitutes redundancy: it enables one portion of the string to be recovered from another, allowing a more concise description. On algorithmic information theory, therefore, a patternless or random string of a certain length has the highest information content of any string of that length. The more randomness a string exhibits, the more information it contains.
Some writers believe that information content ought not to be linked to randomness in this way. As Murray Gell-Mann (Reference Gell-Mann1994, 49–50) points out, algorithmic information theory entails that the collected works of William Shakespeare, which show some degree of regularity, have a smaller information content than a string of gibberish of the same length. Gell-Mann concludes that algorithmic complexity is not a suitable measure of information content.
Instead, Gell-Mann introduces the concept of effective complexity. He assumes that the information content of a string can be divided into two components: an amount of “useful information,” corresponding to the regularity exhibited by the string, and a random component. He defines the effective complexity of an entity as “the length of a concise description of the entity's regularities” (Gell-Mann Reference Gell-Mann1994, 56; see also Gell-Mann Reference Gell-Mann1995; Gell-Mann and Lloyd Reference Gell-Mann and Lloyd1996). In other words, as Gell-Mann makes clear, the effective complexity of a string is defined as the algorithmic complexity of the regular component of the string, neglecting the random component. Gell-Mann claims that effective complexity is a more suitable measure of the information content of a string than algorithmic complexity, because it better captures our intuitive notion of information. He and other writers have applied the concept of effective complexity in the theory of adaptation and control and in quantum mechanics (Lloyd and Slotine Reference Lloyd and Slotine1996; Gell-Mann and Hartle Reference Gell-Mann, Hartle, Feng and Hu1997).
To begin with, we note that the effective complexity of an algorithmically nonrandom string is equal to the string's algorithmic complexity. This is because an algorithmically nonrandom string consists entirely of a regularity or pattern, and exhibits no random component. If the concept of effective complexity is to prove its usefulness, therefore, it will have to be as a measure of the information content of algorithmically random strings.
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.
2. Strings with Empirical Content
Let us begin with strings that admit a physical interpretation, such as empirical data sets in science. Any empirical data set is the effect of the interaction of several different causal factors, including multiple physical phenomena, perturbations, and the behavior of observation or measuring apparatus. The empirical data set contains information about all the causal factors that contributed to its production. This information takes the form of patterns in the data. Each of these patterns may equally legitimately be regarded as constituting the regularity of the data. These patterns have different algorithmic complexities and are exhibited by the data with different noise levels.
For an example, consider a data set on atmospheric temperature. Such a data set exhibits many different patterns (Bryant Reference Bryant1997). These include a pattern with a period of a day, associated with the earth's rotation about its axis; patterns with periods of a few days, associated with the life span of individual weather systems; a pattern with a period of a year, associated with the earth's orbit around the sun; a pattern with a period of 11 years, attributed to the sunspot cycle; a pattern with a period of approximately 21,000 years, attributed to the precession of the earth's orbit; various patterns with periods of between 40,000 and 100,000 years, attributed to fluctuations in the inclination of the earth's axis of rotation and the eccentricity of the earth's orbit; and various patterns with periods of between 107 and 109 years, associated with variations in the earth's rate of rotation, the major geography of the earth, the composition of the atmosphere, and the characteristics of the sun. Each of these patterns has a different algorithmic complexity and is exhibited in the data with a different noise level. Any of these patterns is eligible to be considered as the regularity of the data set. Depending on their cognitive and practical interests, weather forecasters, meteorologists, climatologists, palaeontologists, astronomers, and researchers in other scientific disciplines will regard different patterns in this series as constituting the regularity in the data. They will thus ascribe different values to the effective complexity of the data set.
For a second example, consider a data set consisting of microwave radiation intensity readings of the sky. Radio astronomers analyze such a data set as exhibiting several different patterns (Partridge Reference Partridge1995). One pattern consists of a number of discrete peaks with an intensity of a few kelvin, spread over the sky, corresponding to astronomical radio sources; a second consists of a constant intensity distribution, independent of direction, with the spectrum of a black body at approximately 2.7 K, corresponding to the isotropic background; a third consists of one warm and one cool pole in opposite directions in the sky, corresponding to the dipole anisotropy; a fourth consists of two warm and two cool poles, corresponding to a quadrupole; a fifth consists of fluctuations of radiation temperature on angular scales of 10° and above, called “ripples”; and a sixth consists of fluctuations of radiation temperature on an angular scale of around 1°, dubbed “acoustic oscillations.” Each of these patterns too has a different algorithmic complexity and is exhibited in the data with a different noise level. Any of these patterns is eligible to be considered as the regularity of the data set. Astronomers and cosmologists working on different problems will focus on different patterns in this series, and thus disagree about the effective complexity of the data set.
To summarize, the effective complexity of a string is defined as the algorithmic complexity of the regularity of the string; each of the multiple patterns that may be identified in an empirical data set has equal claim to constitute the regularity of that data set; and each of these patterns has a different algorithmic complexity. It follows that the effective complexity of an empirical data set is not uniquely defined: it varies with the cognitive and practical interests of investigators.
One might attempt to avert this conclusion by defining the effective complexity of a string as the sum of the algorithmic complexities of all the patterns of the string. This attempt does not succeed, however. The set of all regular components of an algorithmically random string is not uniquely defined. It is always possible to analyze the remaining random component of a string as the sum of a particular regularity and a further random component. One of the ways in which science makes empirical progress is precisely by identifying further systematic components in residuals of empirical data sets that were previously considered unanalyzable. The history of research into atmospheric temperature fluctuations and cosmological microwave radiation offers good examples of this.
3. Strings as Formal Constructs
Let us now turn to strings considered as purely formal constructs, lacking physical interpretation. As a formal construct, a string may be described equally legitimately as the sum of any one of infinitely many different patterns and a corresponding noise term. In other words, there are infinitely many distinct descriptions of a given string as “Pattern A + noise at m percent,” “Pattern B + noise at n percent,” and so on through the set of all possible patterns. The patterns in this set have all possible degrees of algorithmic complexity and are exhibited in the string with all possible noise levels. The term “noise” denotes here not a margin of error or factual inaccuracy in a string, but rather the purely mathematical discrepancy between a given pattern and the string, as in classical information theory. Each of these patterns may legitimately be regarded as constituting the regular component of the string. Thus, the effective complexity of the string is arbitrary.
One might attempt to avert this conclusion by devising a nonarbitrary criterion upon which one of the infinitely many mathematically legitimate descriptions of a string is picked out as more adequate than the others. There are just two plausible nonarbitrary criteria upon which one description of the form “Pattern A + noise at m percent” can be picked out as more adequate than the others: one criterion is to pick out the pattern that has the lowest algorithmic complexity, whereas the second is to pick out the pattern that is exhibited in the string with the lowest noise level. Let us examine the consequences of applying these criteria.
Picking out the pattern that has the lowest algorithmic complexity delivers a sequence of zeros (or of ones) as the most adequate description of any string. The difference between this pattern and the actual string—i.e., the entire content of the string—would be described as noise. On this criterion, the effective complexity of any string would be approximately zero.
Picking out the pattern that is exhibited in the string with the lowest noise level delivers the pattern that reproduces the string in every detail as the most adequate description of the string. This pattern is exhibited in the string with zero noise. On this criterion, the effective complexity of any string would be equal to its algorithmic complexity.
All other ways of picking out one of the infinitely many possible descriptions of a string are arbitrary. In particular, any combination of the two criteria mentioned above would depend on their relative weighting and would thereby be arbitrary. Thus, each of the infinitely many other possible descriptions of a string of the form “Pattern A + noise at m percent” has equal status. In other words, every other possible pattern has equal claim to constitute the regularity that the string contains. If the two criteria described above are rejected, therefore, the effective complexity of a string is arbitrary: there is no more justification for assigning one value to it than another (McAllister Reference McAllister1997).
4. Conclusion
The effective complexity of a given string is not uniquely defined. The effective complexity of a string admitting a physical interpretation, such as an empirical data set, depends on the cognitive and practical interests of investigators. The effective complexity of a string regarded as a purely formal construct, lacking a physical interpretation, is either close to zero, or equal to the string's algorithmic complexity, or arbitrary, depending on which of various possible criteria is used to pick out the regular component of the string. Because of these features, effective complexity is not a useful measure of information content. It is a less suitable measure than algorithmic complexity, notwithstanding the counter-intuitive implications of the latter concept.
