DEGREES OF CATEGORICITY AND SPECTRAL DIMENSION
| Autor: | Nikolay Bazhenov, Mars M. Yamaleev, Iskander Sh. Kalimullin |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | The Journal of Symbolic Logic. 83:103-116 |
| ISSN: | 1943-5886 0022-4812 |
| DOI: | 10.1017/jsl.2017.70 |
| Popis: | A Turing degreedis the degree of categoricity of a computable structure${\cal S}$ifdis the least degree capable of computing isomorphisms among arbitrary computable copies of${\cal S}$. A degreedis the strong degree of categoricity of${\cal S}$ifdis the degree of categoricity of${\cal S}$, and there are computable copies${\cal A}$and${\cal B}$of${\cal S}$such that every isomorphism from${\cal A}$onto${\cal B}$computesd. In this paper, we build a c.e. degreedand a computable rigid structure${\cal M}$such thatdis the degree of categoricity of${\cal M}$, butdis not the strong degree of categoricity of${\cal M}$. This solves the open problem of Fokina, Kalimullin, and Miller [13].For a computable structure${\cal S}$, we introduce the notion of the spectral dimension of${\cal S}$, which gives a quantitative characteristic of the degree of categoricity of${\cal S}$. We prove that for a nonzero natural numberN, there is a computable rigid structure${\cal M}$such that$0\prime$is the degree of categoricity of${\cal M}$, and the spectral dimension of${\cal M}$is equal toN. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|