Kraft-Chaitin Inequality Revisited
Cristian S. Calude, Cristian Grozea · Zenodo (CERN European Organization for Nuclear Research) · 1996
: 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]). 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. Keywords: Kraft inequality, Kraft-Chaitin inequality, prefix-free codes. 1 Prerequisites Denote by N = f0; 1; 2; : : :g the set of non-negative integers. If X is a finite set, then #X denotes the cardinality of X . Fix A = fa 1 ; : : : ; aQ g; Q 2, a finite alphabet. By A we denote the set of all strings x 1 x 2 : : : xn with elements x i 2 A (1 i n); the empty string is denoted by . For x in A ; jxj is the length of x (jj = 0). For p 2 N, A p = fx 2 A j jxj = pg is the set of all strings of len...