On 0′-computable reals
George Barmpalias · Electronic Notes in Theoretical Computer Science · 2002
Given a 0′-computable real x we are interested in the relative complexity of the sets Az = {i: zi < x} for possible computable sequences of rationals z = {zs} with limszs = x, with respect to a strong reducibility ≤ = r. It turns out that the r-degree structure of these sets (excluding the trivial, i.e. the finite and co-finite ones) is a substructure of the ≤ = r-degrees inside the Turing degree of x and it can be non-trivial. In fact, we construct a real x = limszs = limsws such that Az∥wttAw. Also, it can be trivial even for non-computable reals x: there is a non-computable c.e. real x such that for all sequences z with limszs = x the sets Az (if co-infinite) have the same m-degree. Assigning such a degree structure to each 0′-computable real we propose the study of the complexity of a single real by means of the complexity of the correspondent degree structure. The variety of these degree structures from real to real indicates that a fine classification of the 0′-computable reals may be possible in this way. Finally, we study the immunity properties of Az: we prove that it cannot be (co-)hyperhyperimmune but it is always bi-hyperimmune or (co-)hypersimple if x is non-computable.