A Hierarchy of Computably Enumerable Reals

• Autorzy: Zheng X.
• Języki publikacji: EN

Abstrakty

EN

Computably enumerable (c.e., for short) reals are the limits of computable increasing sequences of rational numbers. In this paper we introduce the notion of h-bounded c.e. reals by restricting numbers of big jumps in the sequences by the function h and shown an Ershov-style hierarchy of h-bounded c.e. reals which holds even in the sense of Turing degrees. To explore the possible hierarchy of c.e. sets, we look at the h-initially bounded computable sets which restricts number of the changes of the initial segments. This, however, does not lead to an Ershov-style hierarchy. Finally we show a computability gap between computable reals and the strongly c.e. reals, that is, a strongly c.e. real cannot be approximated by a computable increasing sequence of rational numbers whose big jump numbers are bounded by a constant unless it is computable.

Słowa kluczowe

EN

computably enumerably sets; computably enumerable (c.e.) reals; bounded c.e. reals; Ershov's Hierarchy

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 219--230
• Opis fizyczny: bibliogr. 15 poz.

Twórcy

autor

Zheng X.

• Department of Mathematics, University of Cincinnati, Cincinnati, OH 45221, USA,

Bibliografia

• [1] B. S. Cooper. Degrees of I)nsolvability. Ph.D thesis, Leicester University, Leicester, England, 1971.
• [2] R. G. Downey. Some computability-theoretic aspects of reals and randomness. In The Notre Dame lectures, volume 18 of Lect. Notes Log., pages 97-147. Assoc. Symbol. Logic, Urbana, IL, 2005.
• [3] R. G. Downey and D. R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, 200? monograph to be published.
• [4] Y. L. Ershov. A certain hierarchy of sets, i, ii, iii. (Russian). Algebra i Logika, 7(l):47-73, 1968;7(4): 15-47, 1968; 9:34-51,1970.
• [5] E. M. Gold. Limiting recursion. J. Symbolic Logic, 30:28-48, 1965.
• [6] H. Putnam. Trial and error predicates and the solution to a problem of Mostowski. J. Symbolic Logic, 30:49-57,1965.
• [7] R. Rettinger and X. Zheng. A hierarchy of Turing degrees of divergence bounded computable real numbers. J. Complexity, 22(6):818-826,2006.
• [8] R. I. Soare. Cohesive sets and recursively enumerable Dedekind cuts. Pacific J. Math., 31:215-231,1969.
• [9] R. I. Soare. Recursion theory and Dedekind cuts. Trans. Amer. Math. Soc, 140:271-294,1969.
• [10] R. I. Soare. Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.
• [11] K. Weihrauch. Computable Analysis, An Introduction. Springer, Berlin Heidelberg, 2000.
• [12] X.Zheng. Classification of the computably approximable real numbers. Theory of Computing Systems, (to appear).
• [13] X. Zheng. Recursive approximability of real numbers. Mathematical Logic Quarterly, 48(Suppl. 1):131-156, 2002.
• [14] X. Zheng. Computability Theory of Real Numbers. Habilitation's thesis, BTU Cottbus, Germany, Feb., 2005.
• [15] X. Zheng and R. Rettinger. Weak computability and representation of reals. Mathematical Logic Quarterly, 50(4/5):431-442,2004