Home

PyBDM: Python interface to the Block Decomposition Method

The Block Decomposition Method (BDM) approximates algorithmic complexity of a dataset of arbitrary size, that is, the length of the shortest computer program that generates it. This is not trivial as algorithmic complexity is not a computable quantity in the general case and estimation of algorithmic complexity of a dataset can be very useful as it points to mechanistic connections between elements of a system, even such that do not yield any regular statistical patterns that can be captured with more traditional tools based on probability theory and information theory.

Currently 1D and 2D binary arrays are supported, but this may be extended to higher dimensionalities and more complex alphabets in the future.

BDM and the necessary parts of the algorithmic information theory it is based on are described in this paper.

The architecture and the usage of the PyBDM package are described in the README file and dedicated Wiki pages (that may not exist yet). The rest of this page presents a non-exhaustive list of already published research that utilize the BDM or similar techniques based on algorithmic information theory broken down into several general categories.

Foundations of complexity and applications to systems science and dynamical systems

• Input–output maps are strongly biased towards simple outputs
• A constructive approach to the epistemological problem of emergence in complex systems
• Algorithmic Entropy and Landauer’s Principle Link Microscopic System Behaviour to the Thermodynamic Entropy
• Improving Entropy Estimates of Complex Network Topology for the Characterization of Coupling in Dynamical Systems
• An Economy Viewed as a Far-from-Equilibrium System from the Perspective of Algorithmic Information Theory

Cognition, psychology, consciousness, language and neuroscience

• Using Algorithmic Complexity to Differentiate Cognitive States in fMRI
• Bayesian validation of grammar productions for the language of thought

Biology, DNA, evolution, genomics, behaviour, cancer research, boolean and genetic networks

• Trans-algorithmic nature of learning in biological systems
• Symmetry and symmetry breaking in cancer: a foundational approach to the cancer problem

Graphs and networks

• Improving Entropy Estimates of Complex Network Topology for the Characterization of Coupling in Dynamical Systems
• New Deterministic Model of Evolving Trinomial Networks
• On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy
• Spacetime Computing: Towards Algorithmic Causal Sets with Special-Relativistic Properties