Universal Recursively Enumerable Sets of Strings | SpringerLink
Skip to main content

Universal Recursively Enumerable Sets of Strings

  • Conference paper
Developments in Language Theory (DLT 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5257))

Included in the following conference series:

  • 716 Accesses

Abstract

The present work clarifies the relation between domains of universal machines and r.e. prefix-free supersets of such sets. One such characterisation can be obtained in terms of the spectrum function s W (n) mapping n to the number of all strings of length n in the set W. An r.e. prefix-free set W is the superset of the domain of a universal machine iff there are two constants c,d such that s W (n) + s W (n + 1) + ... + s W (n + c) is between 2n − H(n) − d and 2n − H(n) + d for all n; W is the domain of a universal machine iff there is a constant c such that for each n the pair of n and s W (n) + s W (n + 1) + ... + s W (n + c) has at least the prefix-free Description complexity n. There exists a prefix-free r.e. superset W of a domain of a universal machine which is the not a domain of a universal machine; still, the halting probability Ω W of such a set W is Martin-Löf random. Furthermore, it is investigated to which extend this results can be transferred to plain universal machines.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Calude, C.S.: Information and Randomness: An Algorithmic Perspective, 2nd edn., Revised and Extended. Springer, Berlin (2002)

    MATH  Google Scholar 

  2. Calude, C.S., Hertling, P.H., Khoussainov, B., Wang, Y.: Recursively enumerable reals and Chaitin Ω numbers. Theoretical Computer Science 255, 125–149 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  3. Calude, C.S., Staiger, L.: On universal computably enumerable prefix codes. Mathematical Structures in Computer Science (accepted)

    Google Scholar 

  4. Chaitin, G.J.: A theory of program size formally identical to information theory. Journal of the Association for Computing Machinery 22, 329–340 (1975)

    MATH  MathSciNet  Google Scholar 

  5. Chaitin, G.J.: Information-theoretic characterizations of recursive infinite strings. Theoretical Computer Science 2, 45–48 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  6. Chaitin, G.J.: Algorithmic information theory. IBM Journal of Research and Development 21, 350–359+496 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  7. Downey, R., Hirschfeldt, D., LaForte, G.: Randomness and reducibility. Journal of Computer and System Sciences 68, 96–114 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  8. Kjos-Hanssen, B., Merkle, W., Stephan, F.: Kolmogorov Complexity and the Recursion Theorem. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 149–161. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  9. Kolmogorov, A.N.: Three approaches to the definition of the concept “quantity of information”. Problemy Peredachi Informacii 1, 3–11 (1965)

    MATH  MathSciNet  Google Scholar 

  10. Li, M., Vitányi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 2nd edn. Springer, Heidelberg (1997)

    MATH  Google Scholar 

  11. Kučera, A., Slaman, T.: Randomness and recursive enumerability. SIAM Journal on Computing 31, 199–211 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  12. Martin-Löf, P.: The definition of random sequences. Information and Control 9, 602–619 (1966)

    Article  MathSciNet  Google Scholar 

  13. Nies, A.: Computability and Randomness. Oxford University Press, Oxford (to appear)

    Google Scholar 

  14. Odifreddi, P.: Classical Recursion Theory. North-Holland, Amsterdam (1989)

    MATH  Google Scholar 

  15. Schnorr, C.P.: Process complexity and effective random tests. Journal of Computer and System Sciences 7, 376–388 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  16. Solovay, R.: Draft of paper on Chaitin’s work Unpublished notes, 215 pages (1975)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Masami Ito Masafumi Toyama

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Calude, C.S., Nies, A., Staiger, L., Stephan, F. (2008). Universal Recursively Enumerable Sets of Strings. In: Ito, M., Toyama, M. (eds) Developments in Language Theory. DLT 2008. Lecture Notes in Computer Science, vol 5257. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85780-8_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-85780-8_13

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-85779-2

  • Online ISBN: 978-3-540-85780-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics