Abstract:
Assume that a program $p$ produces an output string $b$ for an input string $a$:
$p(a)=b$. We look for a “reduction” (simplification) of $p$, i.e., a program $q$ such that $q(a)=b$
but $q$ has Kolmogorov complexity smaller than $p$ and contains no additional information as
compared to $p$ (this means that the conditional complexity $K(q\mid p)$ is negligible). We show
that, for any two strings $a$ and $b$ (except for some degenerate cases), one can find a nonreducible
program $p$ of any arbitrarily large complexity (any value larger than $K(a)+K(b\mid a)$
is possible).
Fulltext:
PDF file (792 kB)
