Unsimplifiable Descriptions for Kolmogorov Complexity Conditions

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).