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


Oxford University Karolinska Institute John Templeton Foundation Swedish Research Council

 



As seen on the Newsletter of the

 

 


 

 

Content on this site is licensed under a
Creative Commons Attribution 3.0 License

Creative Commons Licence Attribution 3.0 Unported (CC BY 3.0)
View License Deed | View Legal Code