Complexity Explorer Santa Fe Institute


The Online Algorithmic Complexity Calculator

The Online Algorithmic Complexity Calculator (OACC) is an online tool developed by the Algorithmic Nature Group to provide reliable estimations to non-computable functions. This is achieved through various numerical methods based upon the mathematical theory of algorithmic probability and algorithmic randomness. The estimations have a wide range of applications in a range of disciplines from molecular biology, to cognitive science, time series research (e.g. finance), and graph theory (for a list of examples, see Publications). The OACC provides numerical approximations (upper bounds) of Algorithmic (Kolmogorov-Chaitin) Complexity (AC) for short strings (CTM CTM ), for strings of any length (BDM1D BDM 1 D ), and for binary arrays (BDM2D BDM 2 D ), which can represent the adjacency matrices of unweighted graphs. These techniques are not only an alternative to the widespread use of lossless compression algorithms to approximate AC, but true approaches to AC. Lossless compression algorithms (e.g. BZIP2, GZIP, LZ) that are based upon entropy rate are not more related to AC than Shannon Entropy itself, which is unable to compress anything but statistical regularities.

Algorithmic Nature Group
Algorithmic Complexity, Graph Theory, Non-Computable Functions

← Back to Resources