Kolmogorov complexity and generalized length functions

Cameron Fraize, Christopher P. Porter

Kolmogorov complexity measures the algorithmic complexity of a finite binary string $\sigma$ in terms of the length of the shortest description ${\sigma }^{\ast }$ of $\sigma$. Traditionally, the length o…