Measuring Complexity

From: jimruttshow8596

Measuring complexity is a challenging endeavor, with no single, universally agreed-upon method [01:28:19]. When Seth Lloyd began working on this problem in 1986 or 1987, his supervisor at Rockefeller University, Heinz Pagels, challenged him to find a mathematical measure of complexity [01:38:00]. However, Lloyd initially questioned if it was even possible, given that complexity often refers to things that are difficult to characterize and measure [02:04:47].

During a visit to the Santa Fe Institute in 2002, Jim Rut expected to find a single, definitive answer to how to measure complexity, but instead encountered twenty different ideas from twenty different people [02:18:00]. Lloyd himself gave a talk in 1988 titled “31 measures of complexity” highlighting the multitude of approaches [02:37:00].

The world is inherently complex, and few things are truly simple [02:55:00]. Even something as fundamental as an electron requires complex theory to understand [03:02:00], and interactions involving just three electrons quickly become complex, akin to the famous three-body problem in gravity [03:10:00]. Biological systems, such as the metabolism of a bacterium, exemplify high complexity with thousands of interacting chemical reactions and feedback loops [03:40:00].

Fundamentally, the problem of measuring complexity stems from it being a broad class of phenomena rather than a singular, easily quantifiable entity [04:50:00]. Different fields have developed their own specialized measures that work well within their specific domains [05:25:00].

Different Measures of Complexity Different Measures of Complexity

Algorithmic Complexity (Kolmogorov Complexity)

In computer science, a primary measure of complexity is the number of logical operations a computer needs to perform to execute a program [05:32:00]. Algorithmic complexity, also known as Kolmogorov complexity, quantifies the shortest possible computer program required to generate a specific output [08:36:00].

• Pros: Accurately identifies patterns. For example, a sequence of a billion ones (111111...) is considered simple because a short program can generate it [07:33:00].
• Cons: Fails to capture intuitive complexity for random data. A truly random sequence of pixels on a TV screen, or a coin flip sequence, would have very high algorithmic complexity because the shortest “program” is essentially the sequence itself [09:00:00]. However, such random patterns are not intuitively complex [09:59:00].

Shannon Entropy

Shannon entropy is a measure of information, specifically the amount of information required to describe a bit string, taking into account its regularities [10:11:00]. It’s the same formula derived by Maxwell, Boltzmann, and Gibbs in the 19th century to describe physical entropy [11:11:11]. Shannon’s work focused on compressing messages to use bandwidth efficiently, leveraging statistical regularities [11:43:00]. A string of a billion ones is easily compressed, as it has low Shannon entropy [11:57:00].

Logical Depth

Introduced by Charles Bennett, logical depth addresses the limitations of algorithmic complexity [12:14:00]. It measures the number of computational steps a computer must take to produce an output from its shortest possible program [14:47:00].

• Things with low Kolmogorov complexity (like a billion ones) are easy to produce and thus not logically deep [15:08:00].
• Random bit strings have high Kolmogorov complexity but are also not logically deep, as the program is essentially the string itself, which runs quickly [15:20:00].
• The first billion digits of Pi are an example of something with high logical depth [13:03:00]. While there are short programs to generate Pi (like the ancient Greek method of inscribing polygons) [14:03:00], executing these programs to produce many digits takes a long time [15:41:00].
• This concept applies to patterns generated by cellular automata, such as Rule 110, which can produce arbitrarily complex patterns that require all steps to be computed [16:01:00].

Thermodynamic Depth

Defined by Seth Lloyd and Heinz Pagels for Lloyd’s PhD thesis, thermodynamic depth is a physical analog of logical depth [18:48:00]. It measures how much free energy must be consumed and dissipated to assemble a system from its simple description [19:10:00].

• The thermodynamic depth of a bacterial metabolism is enormous because it took billions of years of evolution and immense energy expenditure to produce [19:40:00].
• This measure can be precisely defined mathematically and physically, and can be linked to computational measures through the physics of computation [20:00:00].

Effective Complexity

Developed by Murray Gell-Mann and Seth Lloyd, effective complexity combines physical and computational notions of complexity [21:18:00]. It separates the description of a system into two parts: entropy (random motions) and the algorithmic part (non-random, structured information) [21:52:00]. Effective complexity focuses on the non-random, functional information required to describe a system [22:57:00].

• For a bacterium, its effective complexity would include the organization of its metabolism, DNA, chemical reactions, and how it uses energy for reproduction [24:02:00]. This information is vast (billions of bits for DNA) but much smaller than describing the individual motions of all its atoms and molecules [25:29:00].
• Defining effective complexity requires subjectivity: one must define what information is important for the system’s purpose and setting [26:05:00]. For example, studying an E. coli bacterium in its ecological context within the gut would focus on membranes, inputs, and outputs, rather than detailed internal chemistry [28:28:00].
• This concept often relies on “coarse-graining,” where information below a certain scale is intentionally left out to focus on relevant features [29:17:00].

Fractal Dimensions

Complexity in Various Domains involves the study of nonlinear dynamical systems and fractals [30:22:00]. Fractals are self-similar patterns, like those found in snowflakes, which appear similar at different scales [30:40:00].

• Edward Lorenz’s work on weather patterns demonstrated that while weather is chaotic (tiny differences lead to big outcomes) [31:11:00], its dynamics are confined to a “strange attractor,” a fractal structure [31:31:00].
• Fractal dimensions are useful in describing systems where even if unpredictable in some ways, they are predictable in others due to their underlying low-dimensional fractal structure [34:55:00]. This allows for prediction of weather patterns using macroscopic fluid dynamics equations rather than individual atomic motions [35:06:00].

Lempel-Ziv-Walsh (LZW) Complexity

LZW complexity is a method for adaptive data compression, similar to Shannon’s goal of efficiently encoding messages with regularities [38:14:00].

• It works by building a dictionary and assigning shorter codes to combinations of letters or words that occur more frequently [38:59:00].
• LZW is adaptive, meaning it learns these patterns as it processes the message [39:01:00]. The receiver can deduce the codes on the fly [39:22:00].
• Mathematically, LZW asymptotically approaches the Shannon bound for encoding efficiency as message length increases [39:42:00].
• This algorithm is the basis for common file compression formats like ZIP and GIF [40:13:00]. Applying LZW twice does not improve compression; the compressed form is designed to appear more random, thus less compressible [40:55:00].

Statistical Complexity (Epsilon Machines)

Developed by Jim Crutchfield and Young, statistical complexity measures the size of the simplest computational machine (an automaton) that can reproduce a given message or text with the same statistical regularities [41:15:00].

• An automaton transitions between states, producing outputs, and can be designed to reproduce probabilistic strings [42:15:00].
• Epsilon machines are relevant to modern large language models, which are a form of complex automaton with “attention mechanisms” that identify patterns and relationships within vast datasets [43:25:00].
• These models are incredibly large, require massive computer space and energy to train, and have a significant carbon footprint [44:22:00].

Mutual Information

Mutual information quantifies the information shared between different parts of a complex system made up of multiple subsystems [48:25:00].

• It is calculated as the sum of the information of individual pieces minus the total information of the combined system [49:13:00].
• While a complex system like a bacterium’s metabolism exhibits vast mutual information due to extensive communication and chemical exchanges [50:07:00], mutual information alone is insufficient for complexity. A system where all parts are identical (e.g., a billion identical bits) has high mutual information but is not complex [49:45:00]. It is a necessary but insufficient condition for complexity [50:44:00].

Integrated Information

Integrated information, proposed by Giulio Tononi, is a more intricate form of mutual information [51:31:00]. It measures not only shared information but also the degree to which one can infer the operation of different parts of a system from each other [52:06:00].

• Complex systems like brains or bacteria possess a lot of integrated information [52:18:00].
• However, like mutual information, it’s not a sufficient condition for complexity (or consciousness, as Tononi posits). Error-correcting codes, for instance, have high integrated information because every part of the system carries redundant information about the message, allowing for reconstruction even if parts are damaged [52:41:00]. Yet, error-correcting codes can be quite simple and are not considered conscious [53:09:00].

Network Complexity

Complexity in Various Domains such as networks (communication networks, neural connections, power grids) are important areas of study [57:23:00].

• Network complexity refers to ideas about dealing with complex networks, considering their structure (e.g., power plants of different sizes and types connected in various ways) and dynamics (e.g., electricity flowing across vast distances) [57:51:00].
• These systems can exhibit unforeseen behaviors and tend to have chaotic regimes [58:40:00]. Engineers aim to tune them away from chaos, but when driven to their limits, small changes can lead to unpredictable, complex, and often undesirable emergent behaviors [58:52:00].

Multiscale Entropy

Multiscale entropy relates to the concept of coarse-graining, where a system is viewed at different levels of detail [01:00:20].

• A complex system typically contains a lot of information at each scale [01:01:10]. For example, a human body is complex at macroscopic scales (conversations), cellular scales (individual human cells are highly complex), and even at microscopic scales within cells (e.g., mitochondria) [01:01:27].
• Multiscale entropy indicates how much information is present at these various scales [01:02:17].
• Similar to mutual and integrated information, high multiscale entropy is a symptom of complexity, but not a sole determinant. Simple fractal systems, while having a lot of multiscale information, are not necessarily considered very complex [01:02:38].

Conclusion

The discussion reveals that there is no single measure of complexity that applies universally [01:03:14]. Instead, there are many different measures of complexity, each with its own practical applications and limitations [01:03:20]. The choice of measure often depends on the specific context, purpose, and the level of “coarse-graining” applied to the system under study [02:24:00]. While some measures quantify how hard something is to describe (like entropy or algorithmic information) [00:46:01], others measure how hard it is to produce or do something (like computational complexity or thermodynamic depth) [00:46:20]. Ultimately, the most useful measure is the one that best serves the analytical needs of a particular domain [01:03:52].