matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2023.4.67-80matatecs-32Research ArticleСТАТЬИСтепени селекторных функций и относительная вычислимая категоричностьDegrees of selector functions and relative computable categoricityКалимуллинИ. Ш.KalimullinI. I. Sh.Калимуллин  Искандер  Шагитович Научно-образовательный математический центр ПФО ул. Кремлевская, д. 18, г. Казань, 420008Kalimullin Iskander Shagitovich Volga Region Mathematical Center 18 Kremlyovskaya str., Kazan 420008, Russiaikalimul@gmail.comКазанский (Приволжский) федеральный университетРоссияKazan Federal UniversityRussian Federation202302012024146780Copyright © Калимуллин И.Ш., 20242024Калимуллин И.Ш.Kalimullin I.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/32

Изучаются тьюринговые степени селекторных функций, образующие классы степеней, в которых жесткая вычислимая структура оказывается относительно вычислимо категоричной. Доказывается, что для некоторых структур класс таких степеней может представляться в виде объединения нескольких верхних конусов в.п. степеней. Кроме того, будет установлено, что существуют не-в.п. верхние конусы степеней, реализующиеся классами степеней, в которых вычислимая структура относительно вычислимо категорична.

We study the classes of Turing degrees of selector functions in which a rigid computable structure is relatively computably categorical. It is proved that for some structures such classes of degrees can be represented as the unions of upper cones of c.e. degrees. In addition we show that there are non-c.e. upper cones realized as the degrees in which some computable structure is relatively computably categorical.

вычислимо перечислимые (в.п.) множестваn-в.п. множестватьюринговые степенивычислимые алгебраические структурыотносительнная вычислимая категоричностьселекторные функцииcomputably enumerable (c.e.) setsn-c.e. setsTuring degreescomputable alebrai structuresrelative computable categoricityselector functionsРабота поддержана Фондом развития теоретической физики и математики “БАЗИС”.The work was supported by the Theoretical Physics and Mathematics Advancement Foundation “BASIS”ReferencesC. Ash, J. Knight, M. Manasse, T. Slaman, Generic copies of countable structures, Ann. Pure Appl. Log. 42 (3), 195–205 (1989). DOI: https://doi.org/10.1016/0168-0072(89)90015-8C. Ash, J. Knight, M. Manasse, T. Slaman, Generic copies of countable structures, Ann. Pure Appl. Log. 42 (3), 195–205 (1989). DOI: https://doi.org/10.1016/0168-0072(89)90015-8J. Chisholm, Effective model theory vs. recursive model theory, J. Symb. Log. 55 (3), 1168–1191 (1990). DOI: https://doi.org/10.2307/2274481J. Chisholm, Effective model theory vs. recursive model theory, J. Symb. Log. 55 (3), 1168– 1191 (1990). DOI: https://doi.org/10.2307/2274481C.G. Jockusch, R.A. Shore, Pseudo-jump operators, II: transfinite iterations, hierarchies and minimal covers, J. Symb. Log. 49 (4), 1205–1236 (1984). DOI: https://doi.org/10.2307/2274273C.G. Jockusch, R.A. Shore, Pseudo-jump operators, II: transfinite iterations, hierarchies and minimal covers, J. Symb. Log. 49 (4), 1205–1236 (1984). DOI: https://doi.org/10.2307/2274273M.M. Arslanov, G. LaForte, T.A. Slaman, Relative enumerability in the difference hierarchy, J. Symb. Log. 63 (2), 411–420 (1998). DOI: https://doi.org/10.2307/2586839M.M. Arslanov, G. LaForte, T.A. Slaman, Relative enumerability in the difference hierarchy, J. Symb. Log. 63 (2), 411–420 (1998). DOI: https://doi.org/10.2307/2586839S.B. Cooper, Computability theory, Chapman and Hall/CRC, New York, 2004. DOI: https://doi.org/10.1201/9781315275789S.B. Cooper, Computability theory, Chapman and Hall/CRC, New York, 2004. DOI: https://doi.org/10.1201/9781315275789Р.И. Соар, Вычислимо перечислимые множества и степени, Изд-во Казан. матем. о-ва, Казань, 2000.R. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.

The authors declare that there are no conflicts of interest present.