Abstract:
Kraft's inequality [9] is essential for the classical theory of noiseless coding [1, 8]. In algorithmic
information theory [5, 7, 2] one needs an extension of Kraft's condition from finite sets to (infinite)
recursively enumerable sets. This extension, known as Kraft-Chaitin Theorem, was obtained by
Chaitin in his seminal paper [4] (see also, [3, 2], [10]). The aim of this note is to offer a simpler proof
of Kraft-Chaitin Theorem based on a new construction of the prefix-free code.