JUCS - Journal of Universal Computer Science 2(5): 306-310, doi: 10.3217/jucs-002-05-0306
Kraft-Chaitin Inequality Revisited
Cristian S. S. Calude‡, Cristian Grozea§‡ University of Auckland, Auckland, New Zealand§ Faculty of Mathematics, Bucharest University, Bucharest, Romania
Corresponding author: Cristian S. Calude ( cristian@cs.auckland.ac.nz ) © Cristian S. Calude, Cristian Grozea. This article is freely available under the J.UCS Open Content License. Citation:
Calude CSS, Grozea C (1996) Kraft-Chaitin Inequality Revisited. JUCS - Journal of Universal Computer Science 2(5): 306-310. https://doi.org/10.3217/jucs-002-05-0306 |  |
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]). 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. 1.) C. Calude (ed.). The Finite, the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin Complexity and Applications", Mangalia, Romania, 27 June - 6 July, 1995. 2.) The work of the first author has been partially supported by Auckland University Research Grant A18/ XXXXX/62090/3414050.
Keywords
Kraft inequality, Kraft-Chaitin inequality, prefix-free codes