Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 3 / Issue 11

available in:   PDF (267 kB) PS (89 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-003-11-1226


Surjective Functions on Computably Growing Cantor Sets

Peter Hertling (Department of Computer Science, The University of Auckland, New Zealand)

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.

1 Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov.

Keywords: Cantor sets, Computable maps on infinite sequences, co-r.e. closed sets, computability and measure

Categories: F.1