Search

We study autostability spectra relative to strong constructivizations (SC-autostability spectra). For a decidable structure S, the SC-autostability spectrum of S is the set of all Turing degrees capable of computing isomorphisms among arbitrary decidable copies of S. The degree of SC-autostability for S is the least degree in the spectrum (if such a degree exists). We prove that for a computable successor ordinal α, every Turing degree c.e. in and above 0(α) is the degree of SC-autostability for some decidable structure. We show that for an infinite computable ordinal β, every Turing degree c.e. in and above 0(2β+1) is the degree of SC-autostability for some discrete linear order. We prove that the set of all PA-degrees is an SC-autostability spectrum. We also obtain similar results for autostability spectra relative to n-constructivizations. [ABSTRACT FROM AUTHOR]