Kolmogorov complexity

Remarks

Invariance theorem: for every partial computable $\varphi$ and every $x$, $C(x) \le C_\varphi(x) + \abs{q_\varphi}$. So two choices of $U$ give complexities that differ by at most a constant.

Example: there is a constant $c$ with $C(x) \le \abs{x} + c$ for all $x$, by taking $\varphi$ the identity, which has $C_\varphi(x) = \abs{x}$. For the string $0^n$ of $n$ zeros, $C(0^n) \le \log_2 n + c'$ for a constant $c'$, because a program can read $n$ in binary and print $n$ zeros.

Non-example: $C_{\mathrm{id}}(x) = \abs{x}$, the complexity for the identity function, is not the Kolmogorov complexity. The identity is not universal, and $C_{\mathrm{id}}(0^n) = n$ exceeds $C(0^n)$ by more than any constant.

For each $n$ there is a string $x$ of length $n$ with $C(x) \ge n$, since there are $2^n$ such strings but only $2^n - 1$ strings of length less than $n$. The function $C$ is not computable. A variant, the prefix-free complexity $K$, uses a universal machine whose domain is a prefix-free set.