TY - JOUR

T1 - Categoricity Spectra of Computable Structures

AU - Bazhenov, N. A.

N1 - Publisher Copyright: © 2021, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2021/7

Y1 - 2021/7

N2 - The categoricity spectrum of a computable structure S is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable presentations of S. The degree of categoricity of S is the least degree in the categoricity spectrum of S. This paper is a survey of results on categoricity spectra and degrees of categoricity for computable structures. We focus on the results about degrees of categoricity for linear orders and Boolean algebras. We construct a new series of examples of degrees of categoricity for linear orders.

AB - The categoricity spectrum of a computable structure S is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable presentations of S. The degree of categoricity of S is the least degree in the categoricity spectrum of S. This paper is a survey of results on categoricity spectra and degrees of categoricity for computable structures. We focus on the results about degrees of categoricity for linear orders and Boolean algebras. We construct a new series of examples of degrees of categoricity for linear orders.

KW - 03C57

KW - 03D45

KW - autostability

KW - autostability relative to strong constructivizations

KW - Boolean algebra

KW - categoricity spectrum

KW - computable categoricity

KW - computable structure

KW - decidable categoricity

KW - degree of categoricity

KW - index set

KW - linear order

UR - http://www.scopus.com/inward/record.url?scp=85106673672&partnerID=8YFLogxK

U2 - 10.1007/s10958-021-05419-x

DO - 10.1007/s10958-021-05419-x

M3 - Article

AN - SCOPUS:85106673672

VL - 256

SP - 34

EP - 50

JO - Journal of Mathematical Sciences (United States)

JF - Journal of Mathematical Sciences (United States)

SN - 1072-3374

IS - 1

ER -