The definition of “complexity”
Posted on April 22, 2008
Filed Under Complex Systems |
A question has come up about what exactly is the definition of “complexity”. The motive behind the question is a debate about the impact of complexity on our efforts to build intelligent systems, but the definition is interesting in its own right.
I propose the following as a general definition (or explanation-plus-definition) of “complexity”, where that term is intended in the sense of “complex system”.
1) All systems in the world consist of a number of elements that interact with one another in some way (call these interactions the “local mechanisms”), and as a result the system as a whole has observable characteristics (also called the “global behavior” of the system).
2) Science is about finding systems, observing their global behavior, then trying to discover the local mechanisms that explain that global behavior. [Example: Newton observes the planets following elliptical paths, then explains this by proving that an inverse-square force of gravitation predicts those elliptical paths].
3) As far as we understand it today, the process of finding a scientific explanation is not a formal mathematical process, it is an activity of human minds. (Whether it will ever become a formal procedure in the future is a moot point, in the context of this definition).
4) One aspect of the scientific process is that some explanations are larger than others, in the sense that they take longer to discover, take more space to write down, and take longer to understand. As history progresses, the size of explanations do tend to shrink, but as far as we know these explanations will not all collapse to the same size (quantum electrodynamics will always take longer to understand than universal gravitation), nor will they ever become so small that (for example) human toddlers with today’s brain design will routinely learn QED a couple of weeks after learning to talk. I will refer to this subjective notion of the size of scientific explanations as “theory size”. (The fact that this idea of theory size is subjective, not formalized and measurable, turns out later to be a crucial part of the definition, not just an act of laziness).
5) It is almost tautologous to say that in the history of science so far, theory sizes have not been larger than one-lifetime size when they were initially discovered. But that prompts an interesting question: are there systems for which the simplest explanation is massively larger than that? For example, is there any system that would require a scientist to work full-time for a million years before she could discover the explanation for that system? And, by extension, we can also ask if there are systems for which the theory size is effectively infinite: systems in which there simply is no explanation except the low-level mechanisms?
6) A system is deemed “complex” if the smallest size of a theory that will explain that system is so large that, for today’s human minds, the discovery of that theory is simply not practical. Notice that this definition does not imply that there any such systems in the real world, it just says that if the theory size were ever to go off the scale then the system would (by definition) be complex.
7) The practical problem of deciding whether or not a given system is complex is not trivial. In fact, it is quite easy to show that there cannot be a practical decision procedure that will predict whether a given system is complex. Nevertheless, we can look at the real systems in the world and make two interesting observations. The first is that the vast majority of natural systems are governed by extremely simple local mechanisms, and as practicing scientists we have come across very few cases in which a system could not be analyzed by some means or other, so as to yield a satisfying explanation for its global behavior in terms of its local mechanisms.
The second observation is that we can easily construct, in computers, systems that have local mechanisms with a dramatically different character than the mechanisms seen in low-level aspects of the natural world. These bizarre characteristics can be summarized by the shorthand term “tangled and nonlinear”, but what this means is a combination of nonlinear, memory-dependent, developmental, identity-dependent, and so on (all these terms need to be discussed in more depth elsewhere, but the details are not important at this point). What is interesting about these artificial systems is that their global behavior is sometimes interesting and structured (i.e. not just random mush), but we have no idea, at the moment, how to analyze the local mechanisms to explain their global behavior. Indeed, the experience of most mathematicians is that we may never be able to analyze the local mechanisms to predict the global behavior: these types of system are so far outside the normal realms of mathematical analysis that our success rate on them is almost zero, and most mathematicians would regard them as virtually “untouchable” (my term).
9) Combining the empirical observation about “untouchable” systems with the previous abstract definition of “complex” systems, we come to the following hypothesis:
Hypothesis 1: Systems that are mathematically “untouchable”, and which have global behavior that is structured enough to demand an explanation, are overwhelmingly likely to be “complex”.
This concludes the definition of complexity. In speaking loosely about complex systems, we tend to make an immediate identification between untouchable systems and complex systems — calling them both complex systems — but the strict definition is that these are two separate ideas. It is just that in practice the above hypothesis makes it convenient to conflate the two.
As a final note, it is worth saying that the point of this analysis is that intelligent systems have many characteristics that make us suspect that they can only be built in such a way as to have some degree of untouchability in them, so we can go on to state a second hypothesis:
Hypothesis 2: Intelligent systems contain so many mechanisms that have untouchable aspects, that the problem of explaining intelligent systems (psychology) and the parallel problem of building an intelligent system (artificial intelligence) must both be tackled on the assumption that intelligent systems are complex. (The “Complex Systems Problem”)
Finally, a couple of points about how this relates to other definitions of complexity, and what it means for a system to be partially complex.
The notion of complexity defined here is not identical or derivable from the Chaitin-Kolmogorov notion of complexity, because the latter is based on a strictly formal notion of algorithm complexity, whereas the present definition is about scientific theory size. Part of the reason that these two are not identical is that a self-consistent consequence of the notion of complexity given here is that because scientific discovery is a process carried out by human brains, that process itself is likely to inherit sufficient aspects of complexity to mean that any definition of “theory size” that attempts to be precise and formal would render the present definition self-contradictory. (If you cannot analyze complex systems, how can you assume that the complexity-infected process of scientific discovery can be analyzed to yield a formal definition of “theory size”?).
Can a system be “partially” complex? Of course: systems often have many components and many different types of global behavior that (quite often) can be explained separately. It would be no surprise at all if some systems were a mixture of complex and non-complex. (To take a simple example, many characteristics of fluids can be explained in a non-complex way, but some aspects — such as Reynolds Number and the nature of vortices — appear to be a consequence of complex interactions.
But if a system can be partially complex, how do we measure the “amount” of complexity in the system? The short answer is that don’t: we have no reason to suppose that measuring the exact amount of complexity will ever be feasible. If we were able to plug the specification of a system into some algorithm, and the algorithm were to output a number describing the precise amount of complexity to be expected, or if it were to predict exactly where the complexity was going to manifest itself, the very existence of that algorithm would be a contradiction of the definition of a complex system. The very best we can do is to make an empirical observation about the amount of untouchableness in the characteristics of the system: if the local mechanisms look untouchable, then tread very, very carefully.
This is extremely frustrating, of course. But the frustration should not make us do anything foolish, like pretending that the issue might go away if we deny it.
Comments
10 Responses to “The definition of “complexity””
Leave a Reply
I would very much like to understand what you mean, but doing so will require a dialog. I don’t intend to argue about what you “should” mean or what other people might mean, I am just trying to understand what you mean.
Take a craps table and dice throws on it. Clearly it is made from many interacting parts (the atoms of the objects involved). Clearly there are observable regularities — the die values that show up for a particular throw, things like “cocked dice”, throws that don’t make it far enough to count, dice that bounce off of the table entirely, and so on. What theory can predict the behavior of a particular throw of the dice (that is, predict the global regularity)? If there is an answer at all, it would seem to be “physics plus a complete description of all objects” which makes for a huge “theory size”.
Is this system complex according to what you want to communicate using that term? If not, which aspect of your definition is not met by this system.
Thanks
The meaning of “regularity” is just whatever a scientist would take to be non-random behavior that seems to beg for an ‘explanation”.
So, to take your example, “the die values that show up for a particular throw” is not really a regularity because it is a single event (you used the word “particular” so I took you literally). We can never say of a single event in the world that it constitutes a regularity.
You then mention “cocked dice”. I presume what you are saying is that the dice are no showing expected randomness in their statistics … yes, that constitutes a regularity because it demands an explanation. But this is a very simple regularity, and explaining it does not have to involve more than an appeal to the combination of biassed shape in the dice. This regularity is so weak that it does not illustrate the issues very well. If you insisted that your explanation had to explain the exact reason for the particular bias of the dice, would the explanation be complex? Strictly speaking, yes (the explanation would be too big to practically implement), but this is stretching the idea of explanation beyond its breaking point, as I will now explain.
Explanations are allowed to be pitched at an appropriate level: they do not have to include every single fact about the system. It is valid to explain the general fact that dice thrown in a particular way will bounce off, but nobody can disqualify this as an explanation just because it does not explain every individual thrown in complete detail. We never build “explanations” to work at every level of the cosmos; we always just explain things at what seems to be an appropriate level (see Hofstadter’s “I Am a Strange Loop” for a good recent discussion of this point).
So, when you hear someone give an explanation, it would not be correct to say that they could have given more detail, right down to the molecular level, and then conclude that a ‘real’ theory would have gone all the way down to the molecular level, so therefore all ‘real’ theories have massive theory size.
Nobody says that this concept of “explanation” has to have a formal specification behind it (as you know, scientists do not and can not operate under such formal constraints), so the question should not be “What is the exact definition of a ‘regularity’?” but “Does a particular phenomenon that has been described fit the description of a behavior that is obviously not random, and which therefore would make a curious scientist want to explain it at some level?”
Is “dice that bounce off of the table entirely” a regularity? No: the fact that dice thrown with particular speed and direction will bounce off the table, that is a regularity. Easily explainable by physics in general terms, too difficult to explain the particular events of a given throw, however.
Your final question is about whether the craps table is a complex system. Not the way that it usually operates, it is not, because there are no regularities that are not susceptible to reasonable explanations. As I have just argued, it would make no sense to say that the ‘regularity’ of a single dice throw cannot be explained, because single events are not really regularities by themselves, and because that is asking for too much detail.
If, however, the craps table showed some peculiar behavior like always giving a net dice value that was even on one throw, then odd on the next thrown, and so on, that would be a massive regularity that would jump out at us and demand explanation. If this happened, and there was no way to explain it except by appealing to some factors that were too difficult to analyze then this would be a system that was complex.
However, having said that, notice one thing. We see no evidence of “untouchable” mathematics in its behavior, within which an explanation of the peculiar regularity could be lurking, so we would be deeply upset by such a system. The factors that determine net value of the dice are known, and there is no wiggle room to account for such a result. This makes the example a bad illustration, because in this particular system we would not expect a significant amount of complexity to be involved.
Overall, this is at best a fringe example of a complex system.
Thanks. I will move on to untouchable mathematics once I’m convinced I understand the “complex” idea. If I follow what you said, complexity is not a rigorous mathematical concept, since it appeals for its definition on the sort of things that excite interest in scientists.
Further, the global behavior of interest really only needs explanation in a sort of general way. For example, occasionally the dice on the craps table will bounce entirely out of the table area. That is a regularity, and interesting. It can be explained with some fairly general arguments about momentum, friction, or whatever. That explanation may not allow us to accurately predict the fraction of throws that will behave this way, a numerical result which might require a great deal more explanation and a very large theory, but that’s okay because an explanation does not have to provide such an estimate — and the reason for this is that a reasonable scientist simply doesn’t care about this percentage — it might be 1%, it might be 5%, but really, who cares?. I am not quite comfortable with this because it seems rather arbitrary to me which things need explanation and which don’t, but I can accept the general idea (assuming I’m on the right track for understanding what you’re getting at).
Next: is the process of generating images of the Mandelbrot set complex?
One quick clarification: Let’s suppose that some sort of device is throwing these dice in a fairly consistent force and direction. Still, because of dependence on initial conditions, the path of the dice is only predictable in a general sort of way, and some fraction of the time the dice bounce out of the table entirely. Despite your not thinking this is a regularity, I have to insist that it is: it is kind of amazing that such a radically different result occurs occasionally. To repeat, though, I can accept that it can be “easily” explained (that is, with a small theory) as long as we are not interested in predicting which specific throws will bounce out of the table or making an accurate estimate of what fraction of throws will do so. And I can accept the view that the specific fraction is scientifically unintersting (and therefore does not need explaining with a large theory), with some minor reservations.
Sorry to fill up your blog with posts, hopefully it is not too annoying.
Regarding the Mandelbrot Set question: naively, it seems to me like a great example of complexity — with very interesting global regularities in the images, but it’s not really a “system” in the sense you seem to be talking about…. no bunches of interacting elements, no dynamic “behavior”. With this question I’m trying to probe the sorts of things your definition applies to.
Oh, on the AGI list, Mark Waser (who says he understands your notion of complexity and the argument you are making) writes:
> I am also sure that it applies but don’t
> believe that it is a huge problem unless
> you ignore it. Remember, gravity with
> three bodies is a complex problem
Is that right (gravity with three bodies is a complex problem)? I don’t see what the global regularities demanding explanation would be in the case of the three body problem.
Reading a bit about the three body problem, it appears that scientists and mathematicians do in fact find the three body problem interesting because of certain rare degenerative cases which appear to be treated as global regularities. I’m not completely sure why those cases make the problem complex where the cases of throwing dice that end up, say, with one die on top of another, are not, but I’ll let it pass. Perhaps it is the small size of the theory for solving the degenerative regular cases that makes the general problem complex? That doesn’t seem quite right to me because I get the impression that a reductionistic explanation for some system states is a much different thing than complexity.
But now I’m just confused again. I promise it is not on purpose.
As I seem to be having some success with recent rephrasings of complexity as the term is used in this argument, I’ll quickly attempt to address the confusions I have posted about recently here.
The first issue has to do with whether certain systems (the craps table, an advanced fighter airplane, the three-body gravitational systems, and so on) “are complex”. This depends crucially on the nature of the regularities that an observer finds worth considering (that is, that seem to “demand an explanation”). Among reasonable people with similar goals, there is likely to be agreement about which regularities those are; in other cases, the theory size required may vary greatly depending on the properties that a scientist finds interesting and the degree to which they have to be explained by a theory.
In practice, this relativity will be a cause for heated discussion among individuals, but it should become clear with discussion exactly where disagreement lies: what are the specific local mechanisms of interest? what are the specific global regularities that demand an explanation? what must the explanation do to be satisfying? and then how big does an explanatory theory appear to be? (and thus, how important is complexity to the phenomena under study?)
Regarding the Mandelbrot set, it seems to me that the definition could be extended to cover such abstract entities if desired, but given that the purpose of your argument has little to do with such things, there’s no apparent benefit to screwing around with that.
So, if you think I’ve basically got this stuff right, I can move on to trying to understand untouchable mathematics.
Sorry if I seem sort of idiotic; I find that truly trying to understand somebody else’s ideas from their own point of view is quite difficult unless they magically match up with my own ways of thinking. I suspect it is also often difficult for others also, and the effort is therefore rarely made (unless compelled by school or work).
I am not sure if your above comment came before or after the next post, which tries to answer some of these thoughts.
My only comment here would be to say that, yes, people have different opinions on which ‘regularities’ might need explaining, but that this really does not matter. If a system shows anything more interesting than random behavior, then that behavior could, in principle, be explained. The only question of importance in our context is: are explanations always small enough that human minds can find them and write them down, or could it be that sometimes the smallest possible explanation that can be found (for a particular system) is too large to be feasibly discovered?
That is the only issue that is important. Hypothetically, such systems could exist. See today’s post for more on that.
I posted the comment before I saw the new entry, which will surely be helpful as I continue to think about what you are saying.
I am having some difficulty now reconciling “It is almost always possible to drill down into a system and find some complexity somewhere” with the statement here that the choice of regularities really doesn’t matter… but I’ll think on it further. I’m also at the moment rather uncomfortable with the appeal to “delicate sensibilities” and “tangled” as part of defining “untouchable” mathematics. It might take me a while to reforumulate that in a way that makes sense to my own delicate sensibilities.
I’ll be working on that and following along, but probably with fewer barrages of public bewilderment. Thanks for listening to my questions.