Abstract:
According to the Algorithmic Coding
Theorem, minimal programs of any universal
machine are prefix-codes asymptotically
optimal 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 for any semicomputable
semi-distribution. Finally, a complete
characterization of all machines satisfying
the Algorithmic Coding Theorem is given.