Surjective Functions on Computably Growing Cantor Sets

Show simple item record Hertling, P en 2009-04-16T23:09:52Z en 2009-04-16T23:09:52Z en 1997-10 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-064 (1997) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri 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 en
dc.source.uri 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 en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace