The Online Algorithmic Complexity Calculator

Choosing evaluation parameters for Block Decomposition

If the string that you want to evaluate has length shorter than $13$, you should use the Coding Theorem Method ($\textit{CTM}$) to estimate its algorithmic complexity. Otherwise, you should use the Block Decomposition Method ($\textit{BDM}$), which requires specifying block size and block overlap values if you do not want to use the (optimal) values. The key is to always compare among values with same block size and block overlap values, and not among different ones (as the size and overlap may under- or over-estimate complexity)

The following is a $\textit{BDM}$ partitioning example for block size $= 6$ and block overlap $= 1$ as an illustration of the meaning of block size and block overlap in the estimation of a complexity of a long string:

$\textit{BDM}$ is defined by $$\textit{BDM} = \sum_{i}^{n} \textit{CTM}(\textit{block}_i) + \log_{2}(|\textit{block}_i|),$$ where $\textit{CTM}(\textit{block}_i)$ denotes the approximated algorithmic complexity of the pattern in the block of symbols, and $|\textit{block}_i|$ denotes the number of occurrences (multiplicity) of the block.

You should always pick the largest available block size, as it provides better approximations to algorithmic complexity. In contrast, the smallest block size ($=1$) approximates Shannon Entropy. You can pick any overlapping value that is shorter than your block size. For example, say your string is $111001010111$ and you use block size $=6$. If the overlapping is $0$, then $\textit{BDM}$ will look up the known $\textit{CTM}$ values of $111001$ and $010111$ and add them up, outputting $29.9515$ bits. Alternatively, you can choose block overlap $=1$, for which the strings whose $\textit{CTM}$ values are added are $111001$, $101011$, and $010111$. This second evaluation will output $32.9672$ bits.

Overlapping helps to deal with leftovers of the block partitioning if the string length is not a multiple of the block size, otherwise, leftovers on the borders with length less than the block size will be discarded and won't be considered in the complexity estimation. However, overlapping leads to overestimation and thus is not advised. We have proven in this paper that the error from the underestimation when leaving the borders out of the evaluation converges and is bounded by a fraction of the overall complexity. shows different schemes to deal with boundary conditions. The online calculator only deals with the most 'basic' of these schemes, but we have proven that the error is bounded, and thus the output values are reliable for most comparative purposes. In general, overlapping blocks produce overestimations of complexity, and non-overlapping blocks lead to an underestimation only for objects with dimensions that are not a multiple of the block size.

You should always compare results with the same chosen parameters (unless you estimate the error as we did in this paper and then make corrections or take the deviations into consideration).

As for matrices, the same rule holds. Current support for strings is binary and non-binary, but for arrays it's currently only binary. With some loss of precision, one can always translate any alphabet into binary with some loss of information due to the extra granularity introduced in the translation.

Estimating Algorithmic Probability (AP)

For more technical details you must read the papers listed in the Bibliography Section below. In a nutshell, we calculate a function $D(n,m)(s)$, which estimates the Algorithmic Probability of a string $s$ from a set of halting Turing machines with $n$ states and $m$ symbols denoted by $(n,m)$. We use the standard model of Turing machines used by Tibor Rado in the definition of the Busy Beaver problem, but we have also proven that radical changes to the model produce similar estimations. Beyond the known values of the Busy Beaver problem we have also shown that educated choices of reasonable halting times can be chosen to reach certainty up to any arbitrary statistical significance level.

Formally, $$D(n, m)(s)=\frac{|\{T\in(n, m) : T(p) = s,\ b\in\{0,1,\cdots,m-1\}\}|}{|\{(T,b)\in(n, m)\times \{0,1,\cdots,m-1\} : T(b) \textit{ halts }\}|},$$ where $T(b)$ represents the output of Turing machine $T$ when running on a blank tape filled with symbol $b$ that produces $s$ upon halting, and $|A|$ represents the cardinality of the set $A$.

For $(n,2)$ with $ n < 5 $, the known Busy Beaver values give the maximum number of steps that a machine can run upon halting. But for $n \geq 5$ or for $(n,m)$ with $m > 2$, no Busy Beaver values are known, and the size of the machine spaces make impossible a complete exploration to calculate $D(n,m)$ for arbitrary $n$ and $m$, but an educated choice of timeouts can be made and samples produced (see the bibliography section below).

Approximating Algorithmic Complexity (K) by CTM and BDM

The function $D(n,m)$ is an approximation to Levin's Universal Distribution $\mathfrak{m}(s)$, and it can be used to approximate $K(s)$, the algorithmic complexity of string $s$ by using the Coding Theorem, $$K(s) \simeq -\log_2 \mathfrak{m}(s)$$

The greater value of $n$ we use to calculate $D(n,m)$, the better approximations we make to $K(s)$ for $s$ a string of an alphabet of $m$ symbols. Due to the uncomputability of $D(n,m)$ we work with samples and runtime cutoffs. For the simulation of Turing machines we use a C++ simulator running on a supercomputer of medium size.

$\textit{BDM}$ extends the power of $\textit{CTM}$ as explained in this paper.

Approximating the complexity of non-binary strings or arrays

The calculator allows the use of a number of symbols greater than 2, i.e. non-binary. However, one must take into consideration some factors that may appear non-obvious. When evaluating sequences such as 123456789 you may find that it has not a lower complexity than any other permutation of the same length. This is how Shannon Entropy would also behave yet we are claiming we go beyond Entropy. This is because for a computer program, each individual label for a digit, e.g. the symbol 8, has no meaning. To us, 8 is a number one short from 9 and one above 7, so one can actually reconstruct all the natural numbers from the number. For a Turing machine, 9 is just a symbol and not a number. Yet one would like to identify that 123456789... is of low algorithmic complexity as it is produced by a function such as f(x) = x+1 which certainly can be encoded in a single line of computer code. The easiest way to do this is, surprisingly, transforming each digit into a binary sequence. The result looks like 110111001011101111000... which is simply a binary counter of which there are many more Turing machines and computer programs than most permutations. This is because the binary converter does inject the meaning into the binary sequence.

Approximating Bennett's Logical Depth