BDM

Elixir module that implements the Block Decomposition Method (BDM) developed by Hector Zenil et al to approximate the algorithmic complexity of datasets by decomposing them into smaller blocks and using precomputed CTM (Coding Theorem Method) values.

This implementation is based on PyBDM by Szymon Talaga et al.

Installation

The package can be installed by adding bdm to your list of dependencies in mix.exs:

def deps do
  [
    {:bdm, "~> 0.5.0"}
  ]
end

Key Features

Main Modules and Functions

Usage

bdm = BDM.new(2, 2, 2)

large_matrix = [
  [0, 1, 0, 1, 0, 1],
  [1, 0, 1, 0, 1, 0],
  [0, 1, 0, 1, 0, 1],
  [1, 0, 1, 0, 1, 0],
  [0, 1, 0, 1, 0, 1],
  [1, 0, 1, 0, 1, 0]
]

complexity_2x2 = BDM.compute(bdm, large_matrix)

For more details and explanations, check the Livebook.

How BDM Works

The Block Decomposition Method decomposes an object into smaller parts for which there exist, thanks to CTM, good approximations to their algorithmic complexity, and then aggregates these quantities by following the rules of algorithmic information theory.

Foundation: Coding Theorem Method (CTM)

The Coding Theorem Method (CTM) is a numerical approximation to the algorithmic complexity of single objects.

BDM builds upon the Coding Theorem Method (CTM), which approximates algorithmic complexity using this formula:

$$ K(s) ≈ -log_2(P(s)) $$

where P(s) is the algorithmic probability of string s. CTM approximates algorithmic probability by exploring spaces of Turing machines with n symbols and m states, counting how many produce a given output, and dividing by the total number of machines that halt.

The BDM Process

The Block Decomposition Method operates in three main stages: decomposition, lookup, and aggregation.

Step 1: Precomputation First precompute CTM values for all possible small objects of a given type (e.g. all binary strings of up to 12 digits or all possible square binary matrices up to 4x4) and store them in an efficient lookup table.

Step 2: Decomposition Any arbitrarily large object can be decomposed into smaller slices of appropriate sizes for which CTM values can be looked up very fast. The method partitions the input data into blocks of predetermined sizes.

Step 3: Lookup For each unique slice created during decomposition, the method looks up the precomputed CTM value from the lookup table.

Step 4: Aggregation The CTM values for slices can be aggregated back to a global estimate of Kolmogorov complexity for the entire object using the BDM formula:

$$ BDM(X) = \sum_i{CTM(sᵢ) + log_2(nᵢ)} $$

where:

Boundary Conditions

If the object’s size is not a multiple of the block size, the boundary (or residual) region remains. This module handles two boundary conditions:

Key Advantages

The method essentially transforms an intractable global computation into a series of fast local lookups, making algorithmic complexity estimation practical for real-world datasets.

Citations