Autostability spectra for decidable structures

作者：Bazhenov Nikolay^*

来源：Mathematical Structures in Computer Science, 2018, 28(3): 392-411.

DOI：10.1017/S096012951600030X

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 alpha, every Turing degree c.e. in and above 0((alpha)) is the degree of SC-autostability for some decidable structure. We show that for an infinite computable ordinal beta, every Turing degree c.e. in and above 0((2 beta+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.

• 出版日期2018-3