Surjective Functions on Computably Growing Cantor Sets
Peter H. Hertling · 2020
Abstract: Every in nite 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 in nite sequences there exists a computable mapping which maps a subset of the set onto the whole space of in nite sequences. Cristian Calude asked whether in this result one can replace the positive measure condition by aweaker condition not involving the measure. We show that this is indeed possible: it is su cient 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 e ective than the map constructed by Gacs. Key Words: Computable maps on in nite sequences, co-r.e. closed sets, Cantor sets, computability and measure Category: F.1 1