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 estimations of algorithmic complexity (a.k.a. Kolmogorov-Chaitin complexity) (or $K$) and Algorithmic Probability for short and long strings and for 2-dimensional arrays better than any other tool, and estimations of Bennett's Logical Depth (or $LD$) for strings hitherto impossible to estimate with any other tool. This 3 measures consitute the most powerful and universal algorithmic measures of complexity. 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 upon 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 following labs:

Supported by the following institutions

As seen on the Newsletter of the