Main Page | How It Works | How To Cite | Team | GitHub Repo | Download Data and Tools | Publications

# The Online Algorithmic Complexity Calculator

#### v2.5

The OACC is a powerful online calculator devoted to provide better estimations of Kolmogorov-Chaitin complexity ($K$) for strings and 2-dimensional arrays. It uses a method (called $BDM$) based upon Algorithmic Probability, which is compatible with--but beyond the scope of--lossless compression algorithms that are so widely used to estimate $K$. Implementations of lossless compression are, however, entirely based on Shannon entropy ($S$) (e.g. LZ, LZW, DEFLATE, etc) and thus cannot capture any algorithmic content beyond simple statistical patterns (repetitions).

In contrast, $BDM$ not only considers statistical regularities but is also sensitive to segments of algorithmic nature (such as in a sequence like $12345...$), which $S$ and lossless compression algorithms would be only able to characterize as having maximum randomness and the highest degree of incompressibility. Moreover, unlike $K$ (thanks to the Invariance Theorem) both Entropy and Entropy-based compression algorithms are NOT invariant to language description and are therefore neither suitable nor robust as measures of complexity (find here the arguments & example).

If you use the OACC please cite

The OACC is a project developed by the

Supported by the following institutions

As seen on the Newsletter of the