On Decidable Categoricity and Almost Prime Models

S. S. Goncharov, V. Harizanov, R. Miller

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

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)200-212
Число страниц13
ЖурналSiberian Advances in Mathematics
Том30
Номер выпуска3
DOI
СостояниеОпубликовано - 1 июл 2020

Fingerprint Подробные сведения о темах исследования «On Decidable Categoricity and Almost Prime Models». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать