dc.contributor.author |
Downey, R.G |
en |
dc.contributor.author |
Hirschfeldt, D.R |
en |
dc.contributor.author |
LaForte, G.L |
en |
dc.date.accessioned |
2009-04-16T23:14:35Z |
en |
dc.date.available |
2009-04-16T23:14:35Z |
en |
dc.date.issued |
2001-01 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-148 (2001) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3656 |
en |
dc.description.abstract |
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. 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], Slaman [29], 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. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
en |
dc.title |
Randomness and Reducibility |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |