A string $p$ is called a program to compute $y$ given $x$ if $U(p,x)=y$, where $U$ denotes universal programming language. Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$ is defined as minimum length of a program to compute $y$ given $x$. Let $K(x)$ denote $K(x|\text{empty string})$ (Kolmogorov complexity of $x$) ...
more >>>