 Optimal description machine

A description machine is a partial computable map from finite binary programs to finite binary outputs. It is optimal if, for every other description machine $V$, there is a constant $c_V$ such that $C_U(\sigma )\le C_V(\sigma )+c_V$. Encoding an interpreter index in a fixed prefix gives the constant-overhead descriptions used in incompressibility arguments.