product iamge

Methods and Applications of Algorithmic Complexity: Beyond Statistical Lossless Compression

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

This book explores a different pragmatic approach to algorithmic complexity rooted or motivated by the theoretical foundations of algorithmic probability and explores the relaxation of necessary and sufficient conditions in the pursuit of numerical applicability, with some of these approaches entailing greater risks than others in exchange for greater relevance and applicability.

Some established and also novel techniques in the field of applications of algorithmic (Kolmogorov) complexity currently coexist for the first time, ranging from the dominant ones based upon popular statistical lossless compression algorithms (such as LZW) to newer approaches that advance, complement, and also pose their own limitations. Evidence suggesting that these different methods complement each other for different regimes is presented, and despite their many challenges, some of these methods are better grounded in or motivated by the principles of algorithmic information. 

The authors propose that the field can make greater contributions to science, causation, scientific discovery, networks, and cognition, to mention a few among many fields, instead of remaining either as a technical curiosity of mathematical interest only or as a statistical tool when collapsed into an application of popular lossless compression algorithms. This book goes, thus, beyond popular statistical lossless compression and introduces a different methodological approach to dealing with algorithmic complexity.

For example, graph theory and network science are classic subjects in mathematics widely investigated in the twentieth century, transforming research in many fields of science from economy to medicine. However, it has become increasingly clear that the challenge of analyzing these networks cannot be addressed by tools relying solely on statistical methods. Therefore, model-driven approaches are needed. Recent advances in network science suggest that algorithmic information theory could play an increasingly important role in breaking those limits imposed by traditional statistical analysis (entropy or statistical compression) in modeling evolving complex networks or interacting networks.  Further progress on this front calls for new techniques for an improved mechanistic understanding of complex systems, thereby calling out for increased interaction between systems science, network theory, and algorithmic information theory, to which this book contributes.


Author(s): Hector Zenil, Fernando Soler Toscano, Nicolas Gauvrit
Series: Emergence, Complexity and Computation, 44
Publisher: Springer
Year: 2022

Language: English
Pages: 269
City: Cham

Contents
Part I Theory and Methods
1 Preliminaries
1.1 Computability and the Behavior of Computing Programs
1.1.1 Deterministic Turing Machines
1.1.2 The Theory of Cellular Automata
1.1.3 Elementary Cellular Automata
1.1.4 Wolfram's Classification
1.2 Chance and Classical Probability Theory
1.2.1 Conditional Probability
1.2.2 Shannon's Information Theory
1.2.3 Noisy-Channel Coding Theorem and Redundancy
1.2.4 Bayes' Theorem
1.2.5 Data Compression
1.2.6 Compressibility of Cellular Automata
1.3 Kolmogorov Complexity and Algorithmic Probability
References
2 Enumerating and Simulating Turing Machines
2.1 The Complete Enumeration of (s,k)
2.2 Graphical Representation of Turing Machines
2.3 The Reduced Enumeration
2.4 From Reduced to Complete Enumeration
2.5 Simulating Turing Machines
2.6 Decoding the Enumeration
2.7 Detecting Non-halting Machines
2.7.1 Machines Without Transitions to the Halting State
2.7.2 Detecting Escapees
2.7.3 Detecting Cycles
2.8 Running Machines and Storing the Output Strings
2.8.1 Producing Random Machines
2.9 Halting and Runtime Distributions
2.9.1 Halting History of (2,2) and (3,2) Turing Machines
2.9.2 Returning the Runtime
2.9.3 Two-dimensional Turing Machines
References
3 The Coding Theorem Method
3.1 The Limits of Statistical Compression Algorithms
3.1.1 The Problem of Short Strings
3.2 Approximating the Universal Distribution
3.3 The Empirical Distribution D
3.4 Methodology
3.4.1 Numerical Calculation of D(4)
3.4.2 Algorithmic Probability Tables
3.4.3 Derivation and Calculation of Algorithmic Complexity
3.4.4 Runtimes Investigation
3.5 Calculating D(5)
3.5.1 Setting the Runtime
3.6 A Glance at D(5)
3.7 Reliability of the Approximation of D(5)
3.7.1 Exponential Regression
3.7.2 The Exponential Fit
3.8 Features of D(5)
3.8.1 Lengths
3.8.2 Global Simplicity
3.8.3 Binomial Behavior
3.8.4 A Bayesian Approach
3.9 Comparing D(4) and D(5)
3.9.1 Agreement in Probability
3.9.2 Agreement in Rank
3.10 Kolmogorov Complexity Calculation
3.10.1 Randomness in D(5)
3.10.2 Robustness of K(D(n))
3.11 Validation by the Number of Instructions Used
3.11.1 Logical Depth and K(D(5))
3.12 Summary
References
4 Theoretical Aspects of Finite Approximations to Levin's Semi-measure
4.1 Algorithmic Information Measures
4.2 Turing Machines as a Prefix-Free Set of Programs
4.3 A Levin-Style Algorithmic Measure
4.3.1 Finite Approximations to m
4.3.2 Properties of m and mk
4.4 Computing m5
References
5 Validation and Generalization of CTM
5.1 Multidimensional Complexity
5.2 Deterministic Two-Dimensional Turing Machines
5.3 An Approximation to the Universal Distribution
5.4 Evaluating 2-Dimensional Kolmogorov Complexity
5.5 Cross-Validation of the Coding Theorem Method by Compressibility
5.6 Limitations of Lossless Compression Approaches
5.7 CTM and Compression on Strings of Length 10 to 15
5.8 Comparing 1-Dimensional Strings in (4,2)2D to (4,2)
5.9 Comparison of CTM and Compression of Cellular Automata
References
6 The Block Decomposition Method
6.1 The Use and Misuse of Lossless Compression
6.1.1 Building Upon Entropy Rate
6.2 The Block Decomposition Method
6.2.1 l-Overlapping String Block Decomposition
6.2.2 2- and w-Dimensional Complexity
6.2.3 BDM Upper and Lower Absolute Bounds
6.3 Dealing with Object Boundaries
6.3.1 Recursive BDM
6.3.2 Periodic Boundary Conditions
6.4 Error Estimation
6.4.1 BDM Convergence Towards Shannon Entropy
6.5 Normalized BDM
6.6 Behaviour of CTM to BDM Transition
6.6.1 Smooth BDM (and `Add Col')
6.6.2 Weighted Smooth BDM with Mutual Information
6.7 A Logical Depth-Based Measure
6.8 BDM Asymptotic Time Complexity and Scalability
6.9 Algorithmic Complexity of Integer Sequences
6.10 Summary
References
7 Conditional BDM
7.1 Introduction
7.1.1 On the Second Term
7.2 Joint and Mutual BDM
7.3 The Relationship Between Conditional, Joint and Mutual Information
7.4 Properties and Relationship with Entropy
7.4.1 The Impact of Partition Strategy
7.4.2 Conditional BDM as an Extension of Conditional Entropy
7.5 Numerical Results
7.5.1 Conditional BDM Compared to Conditional Entropy over Biased Distributions
7.5.2 Conditional BDM over Different Partition Sizes
7.6 Distance to Conditional Kolmogorov Complexity
7.7 Hybrid Classical and Algorithmic Conditional BDM
References
Part II Applications
8 Applications to Graph and Network Complexity
8.1 Introduction
8.2 Preliminaries
8.3 Applying BDM to Graphs
8.3.1 Complexity and Graph Vertex Order
8.3.2 Complexity and Edge Density
8.3.3 Graph Duality
8.4 Testing BDM and Boundary Condition Strategies
8.5 Graph Automorphisms and Kolmogorov Complexity
8.6 Applying BDM to Real-World Natural and Social Networks
8.7 The Algorithmic Randomness of Synthetic Complex Networks
8.7.1 Network Connectedness and Complexity
8.7.2 Topological Characterization of Artificial Complex Networks
References
9 Algorithmic Complexity in Cognition
9.1 Working Memory and Intelligence
9.1.1 Participants
9.1.2 Task
9.1.3 Results
9.1.4 Discussion
9.2 Randomness
9.2.1 The Usual Measures of Randomness
9.2.2 Understanding Random ``Biases''
9.2.3 Applications
9.2.4 Comments
9.3 Development
9.3.1 Methods
9.3.2 Modulating Factors
9.3.3 Experiment
9.3.4 Results and Discussion
9.4 Aesthetic Preferences
9.4.1 General Method
9.4.2 Results
9.4.3 Conclusive Discussion
9.5 Visual Cognition
9.5.1 Method
9.5.2 Results and Discussion
9.6 Conspiracy Theories
9.6.1 General Method
9.6.2 Experiment 1
9.6.3 Experiment 2
9.6.4 Experiment 3
9.6.5 General Discussion
9.7 The Emergence of Grammar
9.7.1 Method
9.7.2 Results
9.7.3 Discussion
References
Appendix Source Code of the Turing Machine Simulator
Index