RUS  ENG
Full version
JOURNALS // Itogi Nauki i Tekhniki. Sovremennaya Matematika i ee Prilozheniya. Tematicheskie Obzory // Archive

Itogi Nauki i Tekhniki. Sovrem. Mat. Pril. Temat. Obz., 2018 Volume 157, Pages 42–58 (Mi into406)

This article is cited in 2 papers

Categoricity spectra of computable structures

N. A. Bazhenovab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University

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.

UDC: 510.674, 510.532, 512.56

MSC: 03C57, 03D45


 English version:
Journal of Mathematical Sciences (New York), 2021, 256:1, 34–50

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024