From: jimruttshow8596
The concept of measuring complexity has been a long-standing challenge for researchers, prompting Jim Rutt to note his personal interest in the topic for 25 years without a definitive answer [01:16:00]. As Seth Lloyd, Professor of mechanical engineering at MIT and former Miller Fellow at the Santa Fe Institute, points out, it’s difficult to pinpoint the measure of complexity because “complexity is more a very broad class of things rather than something you can put your finger on” [04:53:00]. Each field tends to develop its own set of measures that work well for its specific context [05:25:00].
General Challenges in Measuring Complexity
The fundamental problem is that complexity is not a single, quantifiable property like mass or temperature [04:50:00]. There are “lots of ways to measure complexity” [01:28:00], and Seth Lloyd once gave a talk titled “31 Measures of Complexity” [02:40:00]. Even simple entities like an electron require complex theory to understand, and adding just a few more elements, like three electrons or three bodies in a gravitational system, quickly leads to complex behavior [03:02:00].
Complexity is often observed at the “border between disorder and Order,” sometimes referred to as the “edge of chaos” [06:10:00]. Systems that are either too ordered (like a salt crystal) or too disordered (like static on a TV screen) are generally not considered complex in an intuitive sense [06:42:00].
Specific Measures of Complexity Across Domains
Algorithmic/Kolmogorov Complexity
This measure, also known as Kolmogorov complexity, quantifies the length of the shortest computer program required to generate a given string of data [08:36:00].
- Highly Ordered Systems: A sequence of a billion “1”s has low algorithmic complexity because it can be generated by a very short program (e.g., “print one a billion times”) [07:30:00].
- Highly Disordered Systems: Random data, like static on a TV screen or a coin flip sequence, has very high algorithmic complexity because the shortest program to reproduce it is essentially a list of all the data points themselves [08:58:00].
A key limitation of algorithmic complexity is that while complex systems should require a lot of information to describe, they “shouldn’t be random” [09:25:00].
Shannon Entropy (Information)
Claude Shannon developed this measure to quantify information for communications, and it turned out to be mathematically identical to the entropy concept from 19th-century physics [10:11:00].
- It measures the amount of information required to describe a bit string, taking into account all its regularities [11:32:00].
- Shannon entropy is closely related to data compression: the more regularities in a message, the more it can be compressed [11:41:00].
Charles Bennett’s Logical Depth
Logical depth attempts to capture the intuitive sense of complexity better than algorithmic complexity by measuring the computational steps required to produce a sequence from its shortest program [13:51:00].
- Example: Pi: The first billion digits of Pi have high logical depth because, while the program to generate them is short (e.g., ancient Greek methods), it takes a long time to compute those digits [14:56:00].
- Cellular Automata: Patterns generated by certain cellular automata, like Rule 110, are considered logically deep because they require running all the computational steps to be produced [16:09:09]. These simple rules can create very complicated or complex patterns, sitting in the “edge of chaos” region [17:48:00].
Thermodynamic Depth (Lloyd & Pagels)
Defined by Seth Lloyd and Hein Pagels, thermodynamic depth is a physical analogue to logical depth [18:48:00]. It measures the physical resources (like free energy) consumed to put a system together from its initial state [19:06:00].
- Example: Bacterial Metabolism: The thermodynamic depth of bacterial metabolism is “humongous” because it took billions of years of evolution and immense energy expenditure through natural selection to produce [19:36:00]. This measure connects physical and computational definitions of complexity [20:00:00].
Effective Complexity (Gell-Mann & Lloyd)
Proposed by Murray Gell-Mann and Seth Lloyd, effective complexity combines physical and computational notions of complexity [21:18:00]. It focuses on the algorithmic part of a system’s description, specifically the non-random, structural information that defines its organization and function, disregarding the purely random parts (entropy) [22:03:00].
- Example: Bacterium Metabolism: For a bacterium, effective complexity would describe its DNA, chemical reactions, energy use, and reproduction processes, which is a very large, non-random amount of information [24:30:00].
- Subjectivity: Defining effective complexity often involves a subjective choice about what aspects of a system are “important” or “functional” (e.g., defining a bacterium’s purpose within its environment) [25:57:00].
- Coarse-Graining: This measure relies on the concept of coarse-graining, where details below a certain scale are intentionally left out to focus on the relevant information at a particular level of observation [29:17:00].
- Engineered Systems: For engineered systems like a car, effective complexity can be defined as the length of the blueprint and descriptions needed to achieve its functional requirements [47:35:00].
Fractal Dimensions
Emerging from the field of nonlinear dynamical systems and chaos theory, fractal dimensions describe patterns that exhibit self-similarity across different scales [30:28:00].
- Example: Weather: Edward Lorenz’s work showed that weather equations are chaotic but confined to a “strange attractor,” a fractal structure [31:31:00]. This indicates that while weather is unpredictable in fine detail, its overall dynamics are confined to a lower-dimensional structure, making it “complex but predictable in other ways” [34:55:00].
Lempel-Ziv Complexity (LZW)
LZW complexity is a method for adaptive data compression, used in algorithms like Zip and GIF [40:10:00].
- It automatically learns frequently occurring patterns in a message and assigns them shorter codes, thereby achieving high compression efficiency [39:01:00].
- Mathematically, it can asymptotically attain Shannon’s bound for encoding efficiency [39:42:00].
Statistical Complexity (Crutchfield & Young’s Epsilon Machines)
Developed by Jim Crutchfield and others, statistical complexity focuses on finding the simplest computational machine (an automaton) that can reproduce a given message or text with the same statistical regularities [41:06:00].
- Epsilon Machines: The Epsilon machine is the size of this simplest automaton, reflecting the inherent “complexity” of the message’s statistical patterns [43:03:00].
- Relevance to LLMs: This concept is relevant to understanding large language models (LLMs), which can be viewed as complex automata trained on vast corpora of text to reproduce statistical patterns of language [43:25:00]. Despite their size and energy consumption, LLMs are still considered “dumb” compared to a human brain [44:50:00].
Mutual Information
Mutual information measures the amount of information that different subsystems of a complex system possess in common [48:37:00].
- It’s a measure of shared information or correlation between parts [49:13:00].
- Necessary but Insufficient: While a complex system (like a bacterium’s metabolism) will typically have a “vast amount of mutual information” due to constant communication and exchange [50:11:00], systems with high mutual information aren’t necessarily complex (e.g., a billion identical bits) [49:50:00].
Integrated Information Theory (Tononi)
Giulio Tononi’s Integrated Information Theory (IIT) is a more intricate form of mutual information, aiming to measure not just shared information but also the extent to which the system’s parts “inform” each other dynamically [51:31:00].
- Claimed Connection to Consciousness: Tononi claims that systems with high integrated information (referred to as “Phi”) are conscious [53:56:00].
- Critique: Critics, including Seth Lloyd, disagree with this direct link, pointing out that simple error-correcting codes can have high integrated information without being conscious [53:40:00]. The debate often centers on the definition of “consciousness” itself [54:51:00].
Network Complexity
This broad class of ideas applies to systems made up of multiple interconnected subsystems, such as communication networks, neural connections in the brain, or the power grid [57:26:00].
- Structure and Dynamics: Network complexity considers the structure of the interconnections (e.g., types and sizes of power plants, transmission lines) and the resulting complex, often unforeseen, dynamical behaviors [58:02:00].
- Chaotic Regimes: Networks can operate in regimes where they exhibit chaotic behavior, which is generally undesirable (e.g., a chaotic electrical grid leading to blackouts) [58:50:00]. Driving these systems to their limits can push them to the “edge of chaos,” leading to complex emergent behaviors [59:07:00].
Multiscale Entropy
Multiscale entropy is closely related to coarse-graining and measures the amount of information present in a system at different observational scales [01:00:20].
- Information Across Scales: Complex systems, particularly living systems or networks, tend to have a large amount of information at each scale, from macroscopic behaviors down to microscopic mechanisms within cells [01:10:00].
- Symptom, Not Cause: Like mutual and integrated information, multiscale entropy is often a symptom of complexity rather than a sole cause; simple fractal systems can also exhibit high multiscale information without being intuitively complex [01:02:50].
In conclusion, there isn’t one universal measure of complexity [01:03:14]. Instead, there are numerous approaches, each with its own utility and applicability depending on the specific domain and purpose of analysis [01:03:52].