Order-Computable Sets
Hirschfeldt, Denis ; Miller, Russell ; Podzorov, Sergei
Notre Dame J. Formal Logic, Tome 48 (2007) no. 1, p. 317-347 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy 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.
Publié le : 2007-07-14
Classification:  order-computability,  computable model theory,  limitwise-monotonic functions,  03D45,  03C57,  03D25,  03D28,  03D30,  68Q30 
@article{1187031407,
     author = {Hirschfeldt, Denis and Miller, Russell and Podzorov, Sergei},
     title = {Order-Computable Sets},
     journal = {Notre Dame J. Formal Logic},
     volume = {48},
     number = {1},
     year = {2007},
     pages = { 317-347},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1187031407}
}

Hirschfeldt, Denis; Miller, Russell; Podzorov, Sergei. Order-Computable Sets. Notre Dame J. Formal Logic, Tome 48 (2007) no. 1, pp.  317-347. http://gdmltest.u-ga.fr/item/1187031407/