Surjective Functions on Computably Growing Cantor Sets
Дата
Авторы
Hertling,Peter
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
Computable maps on infinite sequences , co-r.e. closed sets , Cantor sets , computability and measure