Surjective Functions on Computably Growing Cantor Sets
Surjective Functions on Computably Growing Cantor Sets
复制标题
可计算增长康托集上的满射函数
DOI：
10.3217/jucs-003-11-1226
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Peter Hertling
中科院分区：
文献类型：
--
作者：
Peter Hertling
每一个二进制序列都是图灵可约为一个随机序列。这是P。G。acs的推论，对于每一个co。r。存在一个可计算映射，将集合的一个子集映射到整数序列的整个空间上。christian Calude问，在这个结果中是否可以用一个不涉及测量的较弱的条件来代替积极的测量条件。我们证明，这确实是可能的：只要要求共同存在就足够了。闭集包含一个可计算增长的康托集。此外，对于一个具有正测度的集合，我们构造了一个比G acs构造的映射更有效的满射可计算映射。
Every in nite binary sequence is Turing reducible to a random one. This is a corollary of a result of P eter G acs 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 a weaker 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 G acs.