CODING WITH MINIMAL PROGRAMS
Cristian S. Calude, Hajime Ishihara, Takeshi Yamaguchi · International Journal of Foundations of Computer Science · 2001
According to the Algorithmic Coding Theorem, minimal programs of any universal machine are prefix-codes asymptotically optimal (i.e. optimal up to at most an additive, unknown constant) with respect to the machine algorithmic probabilities. A stronger version of this result will be proven for a class of machines, not necessarily universal, and any semi-distribution. Furthermore, minimal programs with respect to universal machines will be shown to be almost optimal (i.e. optimal up to an additive constant less than or equal to 2) for any semi-computable semi-distribution. Finally, a complete characterization of all machines satisfying the Algorithmic Coding Theorem is given.