From: jimruttshow8596
Measuring complexity is a long-standing challenge, with no single, universally accepted definition or metric [00:01:25]. This difficulty stems from the fact that complexity encompasses a broad class of phenomena that are qualitatively different across various systems [00:04:50]. Each field often develops its own specific measures of complexity that are best suited to its particular problems [00:02:25].
The Challenge of Definition
When asked to develop a mathematical measure of complexity, the initial thought was that if something is hard to characterize and measure, perhaps it’s not possible to define [00:02:04]. Early attempts to define complexity at the Santa Fe Institute yielded many different ideas from various experts [00:02:24]. The sheer number of proposed measures of complexity, reportedly over 31, highlights the diverse perspectives [00:02:40]. The world is inherently complex, and few things are truly simple; even seemingly simple entities like an electron require complex theory to understand [00:02:55].
Different Approaches to Measuring Complexity
Algorithmic (Kolmogorov) Complexity
Algorithmic complexity, also known as Kolmogorov complexity, quantifies the length of the shortest computer program required to generate a given object or sequence [00:08:36].
- Implication: This measure accurately reflects that highly ordered systems, like a billion repetitions of the digit ‘1’, are simple because they can be generated by a very short program [00:07:30].
- Limitation: However, it assigns the highest complexity to completely random sequences, such as static on a TV screen or a billion coin flips [00:08:56]. This clashes with the intuitive understanding that truly random things are not inherently “complex” in a structured sense [00:09:59]. Intuitively, complex systems should require a lot of information to describe but should not be random [00:09:25].
Shannon Entropy
Shannon entropy measures the amount of information required to describe a system or bit string, taking into account its regularities [00:11:51].
- Theoretical Basis: Its formula is identical to the 19th-century thermodynamic entropy, revealing that entropy fundamentally represents the information needed to describe the positions of atoms and molecules [00:11:18].
- Practical Use: It’s highly relevant for data compression, as it quantifies the theoretical limit of how much a message with statistical regularities can be compressed [00:38:00].
Charles Bennett’s Logical Depth
Logical depth measures the computational time required for the shortest program to produce a given output [00:14:47].
- Theoretical Distinction: It distinguishes between things that are easy to produce (like a billion ones, or a random bit string) and those that are computationally “deep” (like the first billion digits of Pi) [00:12:41]. Even with a short program, Pi requires many computational steps [00:15:00].
- Application: This concept applies well to patterns generated by cellular automata, such as “rule 110,” which can produce extremely complex patterns from simple rules, requiring many steps to generate [00:16:10]. These systems sit at the “edge of chaos,” between order and disorder [00:17:48].
Thermodynamic Depth
Defined by Seth Lloyd and Hein Pagels, thermodynamic depth is the physical analog of logical depth [00:18:50].
- Implication: It measures the amount of physical resources, specifically free energy, consumed and dissipated to assemble a system from its actual initial state [00:19:10].
- Application: For example, the metabolism of a bacterium has “humongous” thermodynamic depth because it took billions of years of evolution and vast amounts of energy to produce [00:19:36]. This measure connects the computational and physical definitions of complexity [00:20:00].
Effective Complexity
Developed by Murray Gell-Mann and Seth Lloyd, effective complexity combines computational and physical notions of complexity [00:21:18].
- Theoretical Basis: It focuses on the “non-random stuff” required to describe a system, discarding the purely random information (entropy) [00:22:57]. This requires defining what information is “important” for a given purpose [00:26:05].
- Practical Implications: For a bacterium, effective complexity would describe its metabolic organization, DNA, and functional processes, while ignoring the random motions of individual atoms [00:24:04]. This highlights the need for coarse-graining – defining the relevant level of detail [00:29:17]. In engineering, it quantifies the blueprint length and descriptions needed to meet a system’s functional requirements, such as a car [00:47:35].
Fractal Dimensions
Fractal dimensions are used in the study of nonlinear dynamical systems, including chaos theory [00:30:22].
- Theoretical Relevance: Fractals are self-similar patterns (like snowflakes) found in chaotic systems, such as weather patterns described by the Lorenz attractor [00:30:40]. While chaotic systems are intrinsically unpredictable, the existence of a strange attractor (a fractal structure) means their dynamics are confined and still reveal predictable behaviors within certain bounds [00:31:31].
- Practical Value: Applications include weather prediction, where the inability to calculate every atom’s motion is overcome by understanding fractal structures at various scales [00:35:06].
Lempel-Ziv (LZW) Complexity
LZW complexity is a practical method for data compression that adaptively learns and assigns shorter codes to frequently occurring patterns in a message [00:38:14].
- Practical Implication: It’s the basis for common file compression algorithms like ZIP and GIF [00:40:13]. Asymptotically, LZW achieves the optimal Shannon Bound for encoding efficiency [00:39:42].
- Theoretical Implication: Compressing data transforms regularities into a more random-looking, efficient form. Applying LZW twice does not further compress, but rather expands, as the output of the first compression is designed to look random and therefore incompressible by the same method [00:40:40].
Statistical Complexity (Crutchfield & Young’s Epsilon Machines)
This measure aims to find the simplest computational machine (automaton) that can reproduce a given message or text with the same statistical regularities [00:41:38].
- Theoretical Basis: The “epsilon machine” represents the minimal automaton size to achieve statistical reproduction [00:43:06].
- Contemporary Relevance: This concept is highly relevant to understanding large language models (LLMs), which can be viewed as complex automata trained on vast amounts of data to statistically reproduce text [00:43:25]. Although computationally large and energy-intensive to train, they operate on principles related to statistical complexity [00:44:22].
Mutual Information
Mutual information quantifies the shared information between different parts of a complex system [00:49:13].
- Implication: While a large amount of mutual information is almost certainly a necessary condition for a system to be considered complex (e.g., a bacterium with communicating parts), it is not a sufficient condition [00:49:32]. For example, a billion identical bits have high mutual information but are not complex [00:49:50].
Integrated Information (Tononi)
Integrated information is a more intricate form of mutual information, often discussed in the context of consciousness [00:51:31].
- Theoretical Claim: Proponents suggest that systems with high integrated information are conscious [00:53:56].
- Critique: While complex systems like brains have high integrated information, simple error-correcting codes also exhibit it due to their redundancy, yet are not considered conscious [00:52:41]. This highlights a definitional problem with consciousness itself [00:54:46].
Network Complexity
This category refers to ideas and measures used to deal with complex networks [00:57:55].
- Application: Examples include communication networks, neural connections in the brain, and the power grid [00:57:26].
- Practical Implications: Network complexity can lead to unforeseen behaviors, particularly when systems are driven to their limits, potentially leading to chaotic or unpleasant emergent phenomena [00:58:40]. For instance, the complexity of the power grid makes integrating renewable energy challenging and risks complete collapse under certain conditions [00:57:44].
Multiscale Entropy
Multiscale entropy assesses the amount of information present at different levels of coarse-graining within a system [01:00:20].
- Implication: Complex systems, especially living ones (like humans or individual cells) or networks (like the power grid), typically exhibit a lot of information across multiple scales [01:01:19].
- Limitation: Similar to mutual and integrated information, while a complex system is expected to have high multiscale entropy, systems that are not necessarily complex (e.g., simple fractals) can also exhibit it [01:02:50]. Thus, it’s more of a symptom than a defining characteristic [01:02:56].
Conclusion
Ultimately, there is no single, all-encompassing measure of complexity [01:03:18]. Different measures of complexity are appropriate for different contexts and purposes [00:27:25]. The choice of measure often involves a “purpose question” before any calculation can be made, as the utility of discussing complexity lies in its usefulness for a specific problem [00:28:02]. Users should select the measure that “works for them” given their specific application [01:03:52].