The computable Lipschitz degrees of computably enumerable sets are not dense |
| |
Authors: | Adam R. Day |
| |
Affiliation: | Victoria University of Wellington, New Zealand |
| |
Abstract: | The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex. |
| |
Keywords: | 03D25 03D30 03D32 68Q30 |
本文献已被 ScienceDirect 等数据库收录! |
|