Conditional Kolmogorov complexity

A conditional description machine is a partial computable function $D:\{0,1{\}}^{\ast }\times \{0,1{\}}^{\ast }\rightharpoonup \{0,1{\}}^{\ast },$ with pairs represented through a fixed effective pairing and decoder as in Effective binary encodings and total decoders. Put $C_D(x\mid y):=\min \{\mathrm{\mid }p\mathrm{\mid }:D(p,y)=x\},$ with value $\mathrm{\infty }$ when no such $p$ exists.

A conditional machine $U$ is optimal when, for every conditional machine $D$, there is a constant $c_D$ such that $C_U(x\mid y)\le C_D(x\mid y)+c_D$ for all strings $x,y$. An optimal conditional machine exists by universal dispatch: prefix a program $p$ by a fixed self-delimiting code for an index of $D$ and simulate $D(p,y)$. Fix one such $U$ and write $C(x\mid y):=C_U(x\mid y)$. This is the conditional version of Description machines and plain Kolmogorov complexity.