Natural Large Degree Spectra

Article type: Research Article

Authors: Diamondstone, David^; | Greenberg, Noam | Turetsky, Daniel

Affiliations: Department of Mathematics Victoria University of Wellington Wellington, New Zealand ddiamondstone@gmail.com | Department of Mathematics Victoria University of Wellington Wellington, New Zealand greenberg@msor.vuw.ac.nz http://homepages.mcs.vuw.ac.nz/~greenberg/ | Department of Mathematics Victoria University of Wellington Wellington, New Zealand dan@msor.vuw.ac.nz http://homepages.mcs.vuw.ac.nz/~dan/

Note: [] All authors were supported by the Marsden Fund of New Zealand, Diamondstone and Turetsky as postdoctoral fellows. Greenberg was also supported by a Rutherford Discovery Fellowship.

Abstract: We show that the collection of array non-recursive degrees, the collection of non-jump-traceable degrees, and the collection of degrees which compute a function not dominated by any ω-computably approximable function, are all degree spectra of countable structures.

Keywords: computable structure, degree spectrum, array computable, totally ω-c.a., jump-traceable

DOI: 10.3233/COM-13008

Journal: Computability, vol. 2, no. 1, pp. 1-8, 2013