Abstract:
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$. The paper gives 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 build a new series of examples of degrees of categoricity for linear orders.
Keywords:computable categoricity, categoricity spectrum, degree of categoricity, computable structure, linear order, Boolean algebra, decidable categoricity, autostability, autostability relative to strong constructivizations, index set.