Bounded Computable Enumerability and Hierarchy of Computably Enumerable Reals

摘要

The computable enumerability (c.e., for short) is one of the most important notion in computability theory and is regarded as the first weakening of the computability. In this paper, we explore further possible weakening of computable enumerability. By restricting numbers of possible big jumps in an increasing computable sequence of rational numbers which converges to a c.e. real number we introduce the notion of h-bounded c.e. reals and then shown that it leads naturally to an Ershov-style hierarchy of c.e. reals. However, the similar idea does not work for c.e. sets. We show that there is a computability gap between computable reals and the reals of c.e. binary expansions.