Kolmogorov Complexity

Description:

$\Sigma=\{0,1\}$, a map $f:\Sigma^* \to\Sigma^*$. To describe a string of 0 and 1 $\sigma$, the description is a map so that $f(\tau)=\sigma$.

Kolmogorov complexity $C_f$

$$ C_f(x) = \begin{cases} min\{ \vert p \vert : f(p) = x & \text{if x} \\ \infty & \text{otherwise} \} \end{cases} $$

$f$ can be a universal turing machine.

Published: by ;

Table of Contents

Current Ref:

  • cards/statistics/kolmogorov-complexity.md