Degrees of d. c. e. reals

✍ Scribed by Rod Downey; Guohua Wu; Xizhong Zheng

• Publisher: John Wiley and Sons
• Year: 2004
• Tongue: English
• Weight: 149 KB
• Volume: 50
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.200310103

✦ Synopsis

Abstract

A real α is called a c. e. real if it is the halting probability of a prefix free Turing machine. Equivalently, α is c. e. if it is left computable in the sense that L(α) = {q ∈ ℚ : q ≤ α} is a computably enumerable set. The natural field formed by the c. e. reals turns out to be the field formed by the collection of the d. c. e. reals, which are of the form α—β, where α and β are c. e. reals. While c. e. reals can only be found in the c. e. degrees, Zheng has proven that there are Δ^0^~2~ degrees that are not even n‐c. e. for any n and yet contain d. c. e. reals, where a degree is n‐c. e. if it contains an n‐c. e. set. In this paper we will prove that every ω‐c. e. degree contains a d. c. e. real, but there are ω + 1‐c. e. degrees and, hence Δ^0^~2~ degrees, containing no d. c. e. real. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)