Order-Computable Sets

by Denis R. Hirschfeldt, Russell Miller, and Sergei Podzorov

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.