Methodology 
Turing machine formalism
Consider a Turing machine with alphabet $\Sigma=\{0,1, \cdots, m1\}$ of $m$ symbols and $n$ states $\{1,2, \ldots n\}$ plus an additional Halt state denoted by $0$ (as defined by Rado in his original Busy Beaver paper). The machine runs on a $2$way unbounded tape. At each step:
For the input, we consider machines running on a blank tape (filled with one of the $m$ symbols used as the blank symbol). The output of a halting computation is taken from the contiguous cells on the tape the head of the machine has gone through. Calculating D(n,m)
The function $D(n,m)(s)$ gives the probability that a halting machines in $(n,m)$ produces the output string $s$. Formally, $$D(n, m)(s)=\frac{\{T\in(n, m) : T(p) = s,\ b\in\{0,1,\cdots,m1\}\}}{\{(T,b)\in(n, m)\times \{0,1,\cdots,m1\} : 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 maximim number of steps that a machine can run upon falting. But for $n\geq 5$ or for $(n,m)$ with $m>2$, no Busy Beaver valuer are known, and the size of the machine spaces make impossible a complete exploration to calculate $D(n,m)$, so we make samples.
Approximating $K(s)$
Function $D(n,m)$ is an approximation to Levin's Universal Distribution $\mathfrak{m}(s)$, and it can be used to approach $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.
Bibliography
F. SolerToscano, H. Zenil, J.P. Delahaye and N. Gauvrit, Calculating Kolmogorov Complexity from the Frequency Output Distributions of Small Turing Machines, arXiv:1211.1302 [cs.IT],
See the Publications section for even more details and applications to other areas and connections to other measures.

Content on this site is licensed under a 
Contact info: hectorz at LABORES dot EUCite or attribute as follows: 