A hierarchy of computably enumerable reals

作者：Zheng Xizhong^*

来源：Fundamenta Informaticae, 2008, 83(1-2): 219-230.

• c.e. sets
• c.e. reals
• bounded c.e. reals
• Ershov's Hierarchy

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.

• 出版日期2008
• 单位江苏大学