Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-04T21:23:04.513Z Has data issue: false hasContentIssue false
  • English
  • Français

On universal computably enumerable prefix codes

Published online by Cambridge University Press:  01 February 2009

CRISTIAN S. CALUDE  and
LUDWIG STAIGER
CRISTIAN S. CALUDE
Affiliation:
Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand Email: [email protected]
LUDWIG STAIGER
Affiliation:
Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, D - 06099 Halle, Germany Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study computably enumerable (c.e.) prefix codes that are capable of coding all positive integers in an optimal way up to a fixed constant: these codes will be called universal. We prove various characterisations of these codes, including the following one: a c.e. prefix code is universal if and only if it contains the domain of a universal self-delimiting Turing machine. Finally, we study various properties of these codes from the points of view of computability, maximality and density.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 19 , Special Issue 1: Theory and Applications of Models of Computation (TAMC) , February 2009 , pp. 45 - 57
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Autebert, J.-M., Berstel, J. and Boasson, L. (1997) Context-free languages and pushdown automata. In: Rozenberg, G. and Salomaa, A. (eds.) Handbook of Formal Languages, Vol. 1, Springer-Verlag 111–174.CrossRefGoogle Scholar
Berstel, J. and Perrin, D. (1985) Theory of Codes, Academic Press.Google Scholar
Calude, C. S. (2002) Information and Randomness: An Algorithmic Perspective, 2nd Edition, Revised and Extended, Springer-Verlag.CrossRefGoogle Scholar
Calude, C. S. and Stay, M. A. (2006) Natural halting probabilities, partial randomness, and zeta functions. Inform. and Comput. 204 1718–1739.CrossRefGoogle Scholar
Chaitin, G. J. (1987) Algorithmic Information Theory (3rd printing 1990), Cambridge University Press.CrossRefGoogle Scholar
Downey, R. and Hirschfeldt, D. (to appear) Algorithmic Randomness and Complexity, Springer-Verlag.Google Scholar
Graham, R. L., Knuth, D. E. and Patashnik, O. (1989) Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley.Google Scholar
Kuich, W. (1970) On the entropy of context-free languages. Inform. and Control 16 173–200.CrossRefGoogle Scholar
Levenšteĭn, V. I. (1968) The redundancy and delay of decodable coding of natural numbers. Problemy Kibernet. 20 173–179.Google Scholar
Nies, A. (2007) Personal communication.Google Scholar
Nies, A. (to appear) Computability and Randomness, Oxford University Press.CrossRefGoogle Scholar
Staiger, L. (1993) Kolmogorov complexity and Hausdorff dimension. Inform. and Comput. 103 159–194.CrossRefGoogle Scholar
Staiger, L. (2005) The entropy of Łukasiewicz languages. RAIRO–Theoretical Informatics and Applications 39 (4)621–640.CrossRefGoogle Scholar
Staiger, L. (2007) On maximal prefix codes. Bull. EATCS 91 205–207.Google Scholar
Stănică, P. (2001) Good lower and upper bounds on binomial coefficients. J. Ineq. in Pure and Appl. Math. 2 1–5.Google Scholar
Tadaki, K. (2002) A generalization of Chaitin's halting probability Ω and halting self-similar sets. Hokkaido Math. J. 31 219–253.CrossRefGoogle Scholar
Zvonkin, A. K. and Levin, L. A. (1970) Complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Math. Surveys 25 83–124.CrossRefGoogle Scholar