A Hierarchy of Computably Enumerable Reals

Article type: Research Article

Authors: Zheng, Xizhong

Affiliations: Department of Computer Science, Jiangsu University, Zhenjiang 212013, China and Department of Mathematics, University of Cincinnati, Cincinnati OH 45221-0025, USA. E-mail: xizhong.zheng@uc.edu

Abstract: 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.

Keywords: c.e. sets, c.e. reals, bounded c.e. reals, Ershov's Hierarchy

Journal: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 219-230, 2008