Surjective Functions on Computably Growing Cantor Sets
| dc.creator | Hertling,Peter | |
| dc.date | 1997 | |
| dc.date.accessioned | 2024-02-06T12:49:08Z | |
| dc.date.available | 2024-02-06T12:49:08Z | |
| dc.description | 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. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-003-11-1226 | |
| dc.identifier | https://lib.jucs.org/article/27434/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/7255 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 3(11): 1226-1240 | |
| dc.subject | Computable maps on infinite sequences | |
| dc.subject | co-r.e. closed sets | |
| dc.subject | Cantor sets | |
| dc.subject | computability and measure | |
| dc.title | Surjective Functions on Computably Growing Cantor Sets | |
| dc.type | Research Article |