## Abstract

We study autostability spectra relative to strong constructivizations (SC-autostability spectra). For a decidable structure , the SC-autostability spectrum of is the set of all Turing degrees capable of computing isomorphisms among arbitrary decidable copies of . The degree of SC-autostability for 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.

Original language | English |
---|---|

Pages (from-to) | 392-411 |

Number of pages | 20 |

Journal | Mathematical Structures in Computer Science |

Volume | 28 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1 Mar 2018 |

## Keywords

- STRONG CONSTRUCTIVIZATIONS
- BOOLEAN-ALGEBRAS
- INDEX SETS
- COMPUTABLE CATEGORICITY
- RECURSIVE STRUCTURES
- HYPERARITHMETICAL DEGREES
- LINEAR-ORDERINGS
- MODELS
- COMPLEXITY
- STABILITY