×

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.

MSC:

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
PDFBibTeX XMLCite
Full Text: DOI