Skip to main content
SpringerLink
Log in

Randomness spaces

Extended abstract

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1998)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1443))

Included in the following conference series:

Abstract

Martin-Löf defined infinite random sequences over a finite alphabet via randomness tests which describe sets having measure zero in a constructive sense. In this paper this concept is generalized to separable topological spaces with a measure. We show several general results, like the existence of a universal randomness test under weak conditions, and a randomness preservation result for functions between randomness spaces. Applying these ideas to the real numbers yields a direct definition of random real numbers which is shown to be equivalent to the usual one via the representation of real numbers to some base. Furthermore, we show that every nonconstant computable analytic function preserves randomness. As a second example, by considering the power set of the natural numbers with its natural topology as a randomness space, we introduce a new notion of a random set of numbers. We characterize it in terms of random sequences. Surprisingly, it turns out that there are infinite co-r.e. random sets.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. C. S. Calude, P. Hertling, B. Khoussainov, and Y. Wang. Recursively enumerable reals and Chaitin Ω numbers. In M. Morvan et al., editor, STACS 98, Proceedings, LNCS 1373, pages 596–606, Springer-Verlag, Berlin, 1998.

    Google Scholar 

  2. C. S. Calude and H. Jürgensen. Randomness as an invariant for number representations. In H. Maurer, J. Karhumäki, and G. Rozenberg, editors, Results and Trends in Theoretical Computer Science, pages 44–66. Springer-Verlag, Berlin, 1994.

    Google Scholar 

  3. G. J. Chaitin. On the length of programs for computing finite binary sequences. J. of the ACM, 13:547–569, 1966.

    Article  MATH  MathSciNet  Google Scholar 

  4. G. J. Chaitin. A theory of program size formally identical to information theory. J. of the ACM, 22:329–340, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  5. A. Grzegorczyk. On the definitions of computable real continuous functions. Fund.Math., 44:61–71, 1957.

    MATH  MathSciNet  Google Scholar 

  6. P. Hertling and Y. Wang. Invariance properties of random sequences. J. UCS, 3(11):1241–1249, 1997.

    MATH  MathSciNet  Google Scholar 

  7. K.-I. Ko. Complexity Theory of Real Functions. Birkhäuser, Boston, 1991.

    Google Scholar 

  8. A. N. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1:1–7, 1965.

    MATH  Google Scholar 

  9. C. Kreitz and K. Weihrauch. Theory of representations. Theor. Comp. Science, 38:35–53, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  10. L. A. Levin. Randomness conservation inequalities: information and randomness in mathematical theories. Information and Control, 61:15–37, 1984.

    Article  MATH  MathSciNet  Google Scholar 

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

    MathSciNet  Google Scholar 

  12. M. B. Pour-El and J. I. Richards. Computability in Analysis and Physics. Springer-Verlag, Berlin, Heidelberg, 1989.

    Google Scholar 

  13. C.-P. Schnorr. Zufälligkeit und Wahrscheinlichkeit, volume 218 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1971.

    Google Scholar 

  14. R. I. Soare. Recursively Enumerable Sets and Degrees. Springer-Verlag, Berlin, 1987.

    Google Scholar 

  15. R. J. Solomonoff. A formal theory of inductive inference I, II. Information and Control, 7:1–22, 224–254, 1964.

    Article  MATH  MathSciNet  Google Scholar 

  16. J. Ville. étude Critique de la Notion de Collectif. Gauthier-Villars, Paris, 1939.

    Google Scholar 

  17. R. von Mises. Grundlagen der Wahrscheinlichkeitsrechnung. Mathem. Zeitschrift, 5:52–99, 1919.

    Article  MATH  Google Scholar 

  18. K. Weihrauch. Computability. Springer-Verlag, Berlin, 1987.

    Google Scholar 

  19. K. Weihrauch. A foundation for computable analysis. In D. S. Bridges et al.,editor, Combinatorics, Complexity, and Logic, Proceedings of DMTCS'96, pages 66–89, Springer-Verlag, Singapore, 1997.

    Google Scholar 

  20. A. K. Zvonkin and L. A. Levin. The 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(6):83–124, 1970.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand

    Peter Hertling

  2. Theoretische Informatik I, FernUniversität Hagen, 58084, Hagen, Germany

    Klaus Weihrauch

Authors
  1. Peter Hertling
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Klaus Weihrauch
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Kim G. Larsen Sven Skyum Glynn Winskel

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hertling, P., Weihrauch, K. (1998). Randomness spaces. In: Larsen, K.G., Skyum, S., Winskel, G. (eds) Automata, Languages and Programming. ICALP 1998. Lecture Notes in Computer Science, vol 1443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055103

Download citation

  • DOI: https://doi.org/10.1007/BFb0055103

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

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

  • Online ISBN: 978-3-540-68681-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation