Order-computable sets. (English) Zbl 1146.03030

A set \(A\subseteq\omega\) is called order-computable if the structure \(\langle\omega;<,A\rangle\) has a computable copy. The authors study general properties of order-computable sets, mostly the relationship of this property with Turing degrees. The most impressive result is the fact that there exist computably isomorphic c.e. sets one of which is order-computable and the other is not. Some open questions are formulated.


03D25 Recursively (computably) enumerable sets and degrees
03D28 Other Turing degree structures
03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
Full Text: DOI