Complexity: A Guided Tour by Melanie Mitchell
[Read in July of 2009 but was delayed in writing the review.]
I came across this book during a bookstore trip and decided to purchase it as it included topics related to a couple of recent posts and previously read book, Linked: The New Science of Networks. I'm glad I did as it made me realize that many of the things that I am interested in fall under the domain of Complex Systems.
The book is structured as five parts and nineteen chapters as summarized below:
| PART | CHAPTER | THEME |
|---|---|---|
| 1 | BACKGROUND AND HISTORY | |
| 1 | What is Complexity? | |
| 2 | Dynamics, Chaos, and Prediction | |
| 3 | Information | |
| 4 | Computation | |
| 5 | Evolution | |
| 6 | Genetics, Simplified | |
| 7 | Defining and Measuring Complexity | |
| 2 | LIFE AND EVOLUTION IN COMPUTERS | |
| 8 | Self-Reproducing Computer Programs | |
| 9 | Genetic Algorithms | |
| 3 | COMPUTATION WRIT LARGE | |
| 10 | Cellular Automata, Life, and the Universe | |
| 11 | Computing with Particles | |
| 12 | Information Processing in Living Systems | |
| 13 | How to Make Analogies (if You Are a Computer) | |
| 14 | Prospects of Computer Modeling | |
| 4 | NETWORK THINKING | |
| 15 | The Science of Networks | |
| 16 | Applying Network Science to Real-World Networks | |
| 17 | The Mystery of Scaling | |
| 18 | Evolution, Complexified | |
| 5 | CONCLUSION | |
| 19 | The Past and Future of the Sciences of Complexity |
Part 1, nearly a third of the entire book, provides a thorough introduction to Complex Systems which are defined by the author as having the following properties:
- Complex collective behavior (i.e. the whole is greater than the sum of the parts)
- Signaling and information processing
- Adaptation to environmental changes
Example complex systems cited were insect colonies, the brain, the immune system, economies, and the world wide web.
Chapter 2 was an enjoyable introduction to dynamical systems and chaos theory which I had only a cursory awareness of. The simple "rabbit population" example using logistic maps was a great aid in understanding the concepts of fixed/periodic/strange attractors, and a sensitive dependence on initial conditions (aka. the Butterfly Effect). New to me were the concepts of the period doubling route to chaos and Feigenbaum's Constant (which is just plain odd).
Chapters 3 and 4 covered concepts related to information and computation including: entropy, Maxwell's Demon, statistical mechanics, Shannon's information theory, Hilbert's problems, Godel's incompletness theorem, and Turing machines. Overall the treatment was good and a sufficient introduction for readers unfamiliar with these concepts.
Chapters 5 and 6 discussed the topics of evolution and genetics. I found the discussion on evolution interesting as I don't recall learning about the feud between the early Darwinians, who believed in continuous small variations, and Mendelians, who believed in discrete large variations. I also don't recall learning about the Modern Synthesis or the continued challenges in the form of punctuated equilibrium. Interesting stuff.
Chapter 7 discussed various ways of defining and measuring complexity as:
- size
- entropy
- algorithmic information content
- logical depth
- thermodynamic depth
- computatoinal capacity
- statistical complexity
- fractal dimension
- degree of hierarchy
While no single measure was identified as the measure, all were interesting to consider.
Chapters 8 to 10 discussed cellular automata, genetic algorithms, and artificial life. While the treatment was good, it felt light-weight after having just read The Recursive Universe. That said, Chapter 10 did provide a nice overview of Wolfram's work on cellular automata that augmented the prior material I had read on this subject.
Chapter 11 discussed the use of cellular automata for majority classification tasks. The specific task discussed was the determination of the dominant color in a one-dimensional vector of white and black pixels. The authors used genetic algorithms to evolve a set of CA rules that reliably performed this task by creating diagonal vectors that carried local majority-voting decisions which eventually intersected to produce a majority-vote for the entire original vector. The authors seemed unable to at first understand how the evolved CA worked but I thought it obvious as clearly any solution must involve the horizontal communication of local-majority votes in order to reach a global decision. It seems obvious (to me) that such horizontal communication would manifest as diagonal vectors when the CA evolutions are graphed vertically. I thought the use of particle equations to explain the phenomina was overkill but still interesting.
I enjoyed the author's account in Chapter 13 of her work on the CopyCat program which was designed to process analogies. The problem appears hard and the program was quite clever. I must admit I am extermely jealous that she got to work so closely with Douglas Hofstadter.
Chapters 15 to 16 discussed real-world network theory which included topics such as small-world phenomina, scale-free networks, clustering, preferential association, and network resiliance. Overall the treatment was good but mostly a review after having just read (actually listened to) Barabasi's book Linked, which I highly recommend reading.
Chapters 17 and 18 discussed network theory in the contexts of metabolic scaling and evolution which was very interesting. Some of this material was a review of Stuart Kauffman's work documented in his book Origins of Order. I previously read another of Kauffman's books, At Home in the Universe, which touched on some of the same topics but perhaps I'll add Origins to the list of potential future readings.
Chapter 19 concluded the book with an overview of the state of complexity science and the need for a unifying theory. While the field has accomplished many great things, it appears that a lot of difficult work remains which is perhaps why this is such an appealing topic.
In summary, Complexity is a great book that covers a lot of interesting topics. On a personal level, I am thankful to have read this book because, as I mentioned, it helped me realize that complexity science is the meta-topic that unifies many of my long term interests and therefore serves a guide for future research.
