Order-Computable Sets
Status: published in the Notre Dame
Journal of Formal Logic 48 (2007) 317 - 347.
Availability: journal
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.
drh@math.uchicago.edu