Enumeration Order Equivalence in Rational Numbers

Abstract

The enumeration of elements of c.e. sets in the theory of computability and computational complexity has already been investigated. However, the order of this enumeration has received less attention. The enumeration orders of elements of c.e. sets by means of Turing machines on natural numbers are investigated. In this paper, we consider the enumeration orders of elements of c.e. sets on rational numbers. We present enumeration order reducibility and enumeration order equivalence on rational numbers and propose some lemmas and theorems on these concepts. Also, we show that the theories here hold for Rc and we could repeat the same theories in this domain, in a same way.