A hierarchy of Turing degrees of divergence bounded computable real numbers

摘要

A real number x is f-bounded computable (f-bc, for short) for a function f if there is a computable sequence (x_s) of rational numbers which converges to x f-bounded effectively in the sense that, for any natural number n, the sequence (x_s) has at most f(n) non-overlapping jumps of size larger than 2~(-n). f-bc reals are called divergence bounded computable if f is computable. In this paper we give a hierarchy theorem for Turing degrees of different classes of f-bc reals. More precisely, we will show that, for any computable functions f and g, if there exists a constant γ > 1 such that, for any constant c, f(nγ) + n + c ≤ g(n) holds for almost all n, then the classes of Turing degrees given by f-bc and g-bc reals are different. As a corollary this implies immediately the result of [R. Rettinger, X. Zheng, On the Turing degrees of the divergence bounded computable reals, in: CiE 2005, June 8-15, Amsterdam, The Netherlands, Lecture Notes in Computer Science, vol. 3526, 2005. Springer, Berlin, pp. 418-428.] that the classes of Turing degrees of d-c.e. reals and divergence bounded computable reals are different.