Autostability spectra for decidable structures

Результат исследования: Научные публикации в периодических изданияхстатья

6 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)392-411
Число страниц20
ЖурналMathematical Structures in Computer Science
Том28
Номер выпуска3
DOI
СостояниеОпубликовано - 1 мар 2018

Fingerprint Подробные сведения о темах исследования «Autostability spectra for decidable structures». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать