Lecture Notes in Computer Science, 2007, Volume 4598/2007, 327-337, DOI: 10.1007/978-3-540-73545-8_33

Bounded Computable Enumerability and Hierarchy of Computably Enumerable Reals

Xizhong Zheng

View Related Documents

Abstract

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.

Keywords  c.e. sets - c.e. reals - bounded c.e. reals - Ershov’s Hierarchy

This work is supported by DFG (446 CHV 113/240/0-1) and NSFC (10420130638).

Fulltext Preview

Image of the first page of the fulltext document