This study is based on:
Some differences between equations here and in the mentioned works are based on the fact that we often reduce the symbols to the binary case.
Kolmogorov complexity is defined as the size of the smaller program running on a universal turing machine, that outputs a given string and halts. That is:
$$ K_T(s) = \min\left\{|p|,T(p)=s\right\} $$
A problem with this metric is that it is uncomputable in general, despite being a powerful measure of complexity. This uncomputability is directly related with the halting problem.
Fernando Soler-Toscano (2014) introduces a way to approximate it by combining Levin’s semi-measure - algorithmic probability of a string being produced by a random program - with the coding theorem.
$$ m(s) = \sum_{p:T(p)=s}\frac{1}{2^{|p|}} $$
There is one caveat: to be defined as semi-measure it requires $m(s)\le1$, and this does not happen when we consider the set of all turing machines, since, for instance, one can choose a machine $T$ that outputs $s$ independent of the input, and then
$$ m(s)\ge \sum_{p\in\{0,1\}^*}\frac{1}{2^{|T|+|p|}} = \frac{1}{2^{|T|}}\sum\frac{1}{2^{|p|}} = \infty $$
That is why we define our $m$ (and consequentially our $K$) over the set of prefix-free turing machines. Kraft inequality then gives us the semi-measurability.
<aside> 💡 Prefix-free turing machines are defined as machines that halt, $T(p)=x$, on a set of $p$ values that form a prefix set, that is, no element is prefix of another element. As in Ming&Paul’s “An Introduction to Kolmogorov Complexity and Its Applications”
</aside>
A set $A$ is prefix code set if and only if