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 by the fixed computable pairing $⟨p,y⟩:=1^{\mathrm{\mid }p\mathrm{\mid }}0py\mathrm{.}$ The leading unary length determines the end of $p$, leaving $y$ as the remainder, so both encoding and decoding are Turing computable; in particular this is an effective encoding in the sense of 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. Enumerate conditional machines by their finite Turing-machine codes. On program $1^{\mathrm{\mid }e\mathrm{\mid }}0ep$ and condition $y$, a single conditional machine decodes the machine code $e$ and simulates that machine on $⟨p,y⟩$ using the universal interpreter (A universal Turing machine exists for the chosen coding). For each fixed $D$ choose one of its codes $e$; this adds only $2\mathrm{\mid }e\mathrm{\mid }+1$ bits to $p$, independently of $x,y$. Fix this optimal machine $U$ and write $C(x\mid y):=C_U(x\mid y)$. This is the conditional version of Description machines and plain Kolmogorov complexity.