Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-02T22:11:40.128Z Has data issue: false hasContentIssue false
  • English
  • Français

The method of the Yu–Ding Theorem and its application

Published online by Cambridge University Press:  01 February 2009

YUN FAN
YUN FAN*
Affiliation:
Department of Mathematics, Nanjing University, China and Department of Mathematics, Southeast University, China Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We begin by reviewing the major results dealing with the structure of the cl-degrees, and then focus on the method of the Yu–Ding Theorem, which is an important result in this area. By strengthening the Yu–Ding procedure, we construct a cl-cuppable cl-degree of c.e. sets.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 19 , Special Issue 1: Theory and Applications of Models of Computation (TAMC) , February 2009 , pp. 207 - 215
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barmpalias, G. (2005) Computably enumerable sets in the Solovay and the Strong Weak Truth Table Degrees. In: Proceedings of the CiE conference 2005 conference in Amsterdam. Springer-Verlag Lecture Notes in Computer Science 3526 8–17.CrossRefGoogle Scholar
Barmpalias, G. and Lewis, A. (2006) A c.e. real that cannot be SW-computed by any Ω number. Notre Dame J. Formal Logic 47 (2)197–209.CrossRefGoogle Scholar
Barmpalias, G. and Lewis, A. (2006) The ibT degrees of c.e. sets are not dense. Annals of Pure and Applied Logic Volume 16 (1-2).Google Scholar
Downey, R. G. and Hirschfeldt, D. (to appear) Randomness and reducibility. Springer-Verlag Monographs in Computer Science (in preparation).Google Scholar
Downey, R. G., Hirschfeldt, D. and LaForte, G. (2004) Randomness and reducibility (extended abstract). In: Sgall, J., Pultr, A. and Kolman, P. (eds.) Mathematical Foundations of Computer Science 2001. Springer-Verlag Lecture Notes in Computer Science 2136 316–327. (Final version in Journal of Computing and System Sciences (2004) 68 96–114.)CrossRefGoogle Scholar
Lewis, A. and Barmpalias, G. (2006) Random reals and Lipschitz continunity. Mathematical Structures in Computer Science 16 (5)737–749.CrossRefGoogle Scholar
Lewis, A. and Barmpalias, G. (2007) Randomness and the linear degrees of computability. Annals of Pure and Applied Logic 145 (3)252–257.CrossRefGoogle Scholar
Soare, R. I. (1987) Recursively Enumerable Sets and Degrees, Springer-Verlag.CrossRefGoogle Scholar
Soare, R. I. (to appear) Computability Thoery and Differential Geometry (to appear in The Bulletin of Symbolic Logic).Google Scholar
Yu, L. and Ding, D. (2004) There is no SW-complete c.e. real. J. Symbolic Logic 69 (4)1163–1170.CrossRefGoogle Scholar