Logic Colloquium 2008
Barbara F. Csima Degree spectra of almost computable structures
A countable algebraic structure is almost computable if almost every Turing degree can compute a copy of the structure; in other words, if the degree spectrum of the structure has measure 1 under the standard measure on the Cantor space. We give examples of almost computable structures the complements of degree spectra of which are uncountable. Moreover, we give an example of a structure whose degree spectrum coincides with the hyperimmune degrees.
back