2001 | OriginalPaper | Buchkapitel
Randomness and Reductibility
verfasst von : Rod G. Downey, Denis R. Hirschfeldt, Geoff La Forte
Erschienen in: Mathematical Foundations of Computer Science 2001
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
How random is a real? Given two reals, which is more random? If we partition reals into equivalence classes of reals of the “same degrees of randomness”, what does the resulting structure look like? The goal of this paper is to look at questions like these, specifically by studying the properties of reducibilities that act as measures of relative randomness, as embodied in the concept of initial-segment complexity. One such reducibility, called domination or Solovay reducibility, was introduced by Solovay [34], and has been studied by Calude, Hertling, Khoussainov, and Wang [8], Calude [3], Kučera and Slaman [22], and Downey, Hirschfeldt, and Nies [15], among others. Solovay reducibility has proved to be a powerful tool in the study of randomness of effectively presented reals. Motivated by certain shortcomings of Solovay reducibility, which we will discuss below, we introduce two new reducibilities and study, among other things, the relationships between these various measures of relative randomness.