TY - JOUR

T1 - On Decidable Categoricity and Almost Prime Models

AU - Goncharov, S. S.

AU - Harizanov, V.

AU - Miller, R.

PY - 2020/7/1

Y1 - 2020/7/1

N2 - The complexity of isomorphisms for computable and decidable structures plays animportant role in computable model theory. Goncharov [26] defined the degree ofdecidable categoricity of a decidable model (M to be the least Turing degree, if it exists, which iscapable of computing isomorphisms between arbitrary decidable copies of (M. If this degree is 0, we say that the structure (M is decidablycategorical. Goncharov established that every computably enumerable degree is thedegree of categoricity of a prime model, and Bazhenov showed that there is a prime model with nodegree of categoricity. Here we investigate the degrees of categoricity of various prime models withadded constants, also called almost prime models. Werelate the degree of decidable categoricity of an almost prime model (M to the Turing degree of the set C(M) of complete formulas. We also investigate uniformdecidable categoricity, characterizing it by primality of (M and Turing reducibility of C(M) to the theory of (M.

AB - The complexity of isomorphisms for computable and decidable structures plays animportant role in computable model theory. Goncharov [26] defined the degree ofdecidable categoricity of a decidable model (M to be the least Turing degree, if it exists, which iscapable of computing isomorphisms between arbitrary decidable copies of (M. If this degree is 0, we say that the structure (M is decidablycategorical. Goncharov established that every computably enumerable degree is thedegree of categoricity of a prime model, and Bazhenov showed that there is a prime model with nodegree of categoricity. Here we investigate the degrees of categoricity of various prime models withadded constants, also called almost prime models. Werelate the degree of decidable categoricity of an almost prime model (M to the Turing degree of the set C(M) of complete formulas. We also investigate uniformdecidable categoricity, characterizing it by primality of (M and Turing reducibility of C(M) to the theory of (M.

KW - almost prime model

KW - complete formula

KW - computable model

KW - decidable model

KW - decidable theory

KW - degree of decidable categoricity

KW - prime model

KW - Turing degree

KW - uniform decidable categoricity

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

U2 - 10.3103/S1055134420030050

DO - 10.3103/S1055134420030050

M3 - Article

AN - SCOPUS:85089529243

VL - 30

SP - 200

EP - 212

JO - Siberian Advances in Mathematics

JF - Siberian Advances in Mathematics

SN - 1055-1344

IS - 3

ER -