dc.contributor.author |
Downey, R.G |
en |
dc.contributor.author |
Hirschfeldt, D.R |
en |
dc.contributor.author |
Nies, A |
en |
dc.date.accessioned |
2009-04-16T23:15:21Z |
en |
dc.date.available |
2009-04-16T23:15:21Z |
en |
dc.date.issued |
2000-09 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-144 (2000) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3652 |
en |
dc.description.abstract |
We study effectively given positive reals (more specifically, computably enumerable reals) under a measure of relative randomness introduced by Solovay [30]
and studied by Calude, Hertling, Khoussainov, and Wang [6], Calude [2], Slaman [26], and Coles, Downey, and LaForte [12], among others. This measure is
called domination or Solovay reducibility, and is defined by saying that α
dominates β if there are a constant c and a partial computable function φ such that
for all positive rationals q < α we have φ(q) ↓< β and β - φ(q) ≤ c(α-q). The
intuition is that an approximating sequence for α generates one for β. It is not
hard to show that if α dominates β then the initial segment complexity of α is at
least that of β.
In this paper we are concerned with structural properties of the degree structure generated by Solovay reducibility. We answer a long-standing question in
this area of investigation by proving the density of the Solovay degrees. We also
provide a new characterization of the random c.e. reals in terms of splittings in
the Solovay degrees. Specifically, we show that the Solovay degrees of computably
enumerable reals are dense, that any incomplete Solovay degree splits over any
lesser degree, and that the join of any two incomplete Solovay degrees is incomplete, so that the complete Solovay degree does not split at all. The methodology
is of some technical interest, since it includes a priority argument in which the
injuries are themselves controlled by randomness considerations. |
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, Computability, and Density |
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 |