Status: published in the Notre Dame
Journal of Formal Logic 48 (2007) 317 - 347.
version and preprint
Abstract. We give a straightforward computable-model-theoretic
definition of a property of Δ02 sets, called
order-computability. We then prove various results about these
sets which suggest that, simple though the definition is, the property
defies any characterization in pure computability theory. The most
striking example is the construction of two computably isomorphic
c.e. sets, one of which is order-computable and the other not.