The Redundancy of a Computable Code on a Noncomputable Distribution

Łukasz Dębowski

We introduce new definitions of universal and superuniversal computable codes, which are based on a code's ability to approximate Kolmogorov complexity within the prescribed margin…