- Page of Pablo Funes' PhD thesis
What is complexity?
What is complexity?: The question is very much too vast to be answered in something smaller than a whole book. I am planning on dedicating an entire post about measuring complexity with a range of metrics that people have come up with in the past. A big question I’m asking myself is: “How much does complexity depend on subjectivity and the observer?”
Complexity is about studying systems and models which components interact in multiple ways and according to local rules. This very general framework is often called complex systems.
Complexity has various meanings depending on the fields and therefore can be applied to a wide range of systems.
However, its lack of clear definition makes it difficult to measure and estimate. The concept of complexity is hard to study in practice for a given system.
Complex systems are systems made of many components that interact together. They usually exhibit behaviors that can be labeled as complex.
Complexity and order
A.N. Whitehead on “Ideal Opposites” in Process and Reality:
Order is not sufficient. What is required, is something much more complex. It is order entering upon novelty; so that the massiveness of order does not degenerate into mere repetition; and so that the novelty is always reflected upon a background of system.
The study of complexity is often linked to the study of emergence and self-organization. They terms often refer to the spontaneous apparition of complex structures in a system made of simpler components.
Features of a complex process
From (Grassberger 1989)
- Between disorder and order. Hard to describe and not just random structures.
- Often involve hierarchies
- Feeback loops, for example from lower levels of the hierarchy.
- Higher-level concepts arise without being put in explicitely.
- Complex systems are composed of many parts with strong and non-trivial correlations between these parts. Are they spontaneous or do they need to be encoded? (GOL glider gun vs. spontaneous spaceships in some rules)
- Correlations between the object and its environment. Examples: complexity of DNA exists because of its correlation with the reading machinery, and the protein building machinery, etc. up to the whole organism.
- It has meaning, meaning that only some of the features of the system are essentials, and one can create a compressed on more “intelligent” description. Therefore this could be related to compressibility.
Complexity growth in living systems
Complexity doesn’t have to grow in living systems. And believing that living organisms evolve towards greater complexity is a common fallacy in the study of biological evolution.
- First, living systems do not evolve in response to environmental changes, and Earth’s history has shown that going extinct is for instance a much more common response to environmental changes. Species survive environmental changes because they happen to have some parts of its population with an evolutionary advantage compared to other species.
- According to some, complexity therefore does not necessarily increase in living organisms that evolve, because the path to survival to environmental change might actually be a decrease in complexity (e.g number of bones in the jaw see this link). This is not the opinion supported by many older works as explained in (McShea 1991) .
- Talk: Alife 2020 keynote Lee Cronin - A Top Down Chemically Embodied Artificial Life Computation
- Complexity of cellular automata
- Cellular automata
- Lempel-Ziv-Welch algorithm
- Notes on: The Architecture of Complexity by Simon, H. A. (1962)
- Notes on: More Is Different by Anderson, P. W. (1972)
- Notes on: Evolved Open-Endedness, Not Open-Ended Evolution by Pattee, H. H., & Sayama, H. (2019)
- Notes on: Complexity and evolution: What everybody knows by McShea, D. W. (1991)
- Complexity metrics
- Surprisingly Turing-Complete
- Algorithmic probability
- Open-ended Evolution
- Kolmogorov complexity
- Minimum description length