Solovay Reducibility on D-c.e Real Numbers
A c.e. real x is Solovay reducible to another c.e. real y if x can be approximated at least as efficiently as y by means of increasing computable sequences of rational numbers. The Solovay reducibility classifies elegantly the relative randomness of c.e. reals. Especially, the c.e. randoM reals are complete unter the Solovay reducibility for c.e. reals. In this paper we investigate an extension of the Solovay reducibility to the △02-reals and show that the c.e. random reals are complete under (extended) Solovay reducibility for d-c.e. reals too. Actually we show that only the d-c.e. reals can be Solovay reducible to an c.e. random real. Furthermore, we show that this fails for the class of divergence bounded computable reals which extends the class of d-c.e. reals properly. In addition, we show also that any d-c.e. random reals are either c.e. or co-c.e.
Robert Rettinger Xizhong Zheng
Theoretische Informatik II, FernUniversitat Hagen, D-58084 Hagen, Germany Department of Computer Science, Jiangsu University, Zhenjiang 212013, China Theoretische Informatik,
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
359-368
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）