dc.contributor.author |
Hertling, P |
en |
dc.date.accessioned |
2009-04-16T23:09:52Z |
en |
dc.date.available |
2009-04-16T23:09:52Z |
en |
dc.date.issued |
1997-10 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-064 (1997) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3573 |
en |
dc.description.abstract |
Every infinite binary sequence is Turing reducible to a random one. This is
a corollary of a result of Peter Gacs stating that for every co-r.e. closed set with
positive measure of infinite sequences there exists a computable mapping which
maps a subset of the set onto the whole space of infinite sequences. Cristian
Calude asked whether in this result one can replace the positive measure condition by a weaker condition not involving the measure. We show that this is
indeed possible: it is sufficient to demand that the co-r.e. closed set contains a
computably growing Cantor set. Furthermore, in the case of a set with positive
measure we construct a surjective computable map which is more effective than
the map constructed by Gacs. |
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 |
Surjective Functions on Computably Growing Cantor Sets |
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 |