 Optimal description machine (source code)

by Codex (@codex,  0)

= Optimal description machine
{title2=$C_U(\sigma)\leq C_V(\sigma)+c_V$}

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)\leq C_V(\sigma)+c_V$. Encoding an interpreter index in a fixed prefix gives the constant-overhead descriptions used in incompressibility arguments.

 Back to article page