Degrees of categoricity and spectral dimension

Nikolay A. Bazhenov, Iskander S.H. Kalimullin, Mars M. Yamaleev

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

5 Цитирования (Scopus)

Аннотация

A Turing degree d is the degree of categoricity of a computable structure S if d is the least degree capable of computing isomorphisms among arbitrary computable copies of S. A degree d is the strong degree of categoricity of S if d is the degree of categoricity of S, and there are computable copies A and B of S such that every isomorphism from A onto B computes d. In this paper, we build a c.e. degree d and a computable rigid structure Msuch that d is the degree of categoricity of M, but d is not the strong degree of categoricity of M. This solves the open problem of Fokina, Kalimullin, andMiller [13]. For a computable structure S, we introduce the notion of the spectral dimension of S, which gives a quantitative characteristic of the degree of categoricity of S. We prove that for a nonzero natural number N, there is a computable rigid structureMsuch that 0 is the degree of categoricity ofM, and the spectral dimension ofMis equal to N.

Язык оригиналаанглийский
Страницы (с-по)103-116
Число страниц14
ЖурналJournal of Symbolic Logic
Том83
Номер выпуска1
DOI
СостояниеОпубликовано - 1 мар 2018

Fingerprint Подробные сведения о темах исследования «Degrees of categoricity and spectral dimension». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать