Степени селекторных функций и относительная вычислимая категоричность
https://doi.org/10.26907/2949-3919.2023.4.67-80
Аннотация
Изучаются тьюринговые степени селекторных функций, образующие классы степеней, в которых жесткая вычислимая структура оказывается относительно вычислимо категоричной. Доказывается, что для некоторых структур класс таких степеней может представляться в виде объединения нескольких верхних конусов в.п. степеней. Кроме того, будет установлено, что существуют не-в.п. верхние конусы степеней, реализующиеся классами степеней, в которых вычислимая структура относительно вычислимо категорична.
Ключевые слова
вычислимо перечислимые (в.п.) множества,
n-в.п. множества,
тьюринговые степени,
вычислимые алгебраические структуры,
относительнная вычислимая категоричность,
селекторные функции
При поддержке: Работа поддержана Фондом развития теоретической физики и математики “БАЗИС”.
Об авторе
И. Ш. Калимуллин
Казанский (Приволжский) федеральный университет
Россия
Калимуллин Искандер Шагитович
Научно-образовательный математический центр ПФО
ул. Кремлевская, д. 18, г. Казань, 420008
Россия
Калимуллин Искандер Шагитович
Научно-образовательный математический центр ПФО
ул. Кремлевская, д. 18, г. Казань, 420008
Список литературы
1. C. 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-8
2. J. Chisholm, Effective model theory vs. recursive model theory, J. Symb. Log. 55 (3), 1168–1191 (1990). DOI: https://doi.org/10.2307/2274481
3. C.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/2274273
4. M.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/2586839
5. S.B. Cooper, Computability theory, Chapman and Hall/CRC, New York, 2004. DOI: https://doi.org/10.1201/9781315275789
6. Р.И. Соар, Вычислимо перечислимые множества и степени, Изд-во Казан. матем. о-ва, Казань, 2000.
Рецензия
Для цитирования:
Калимуллин И.Ш. Степени селекторных функций и относительная вычислимая категоричность. Математика и теоретические компьютерные науки. 2023;1(4):67-80. https://doi.org/10.26907/2949-3919.2023.4.67-80
For citation:
Kalimullin I.I. Degrees of selector functions and relative computable categoricity. Mathematics and Theoretical Computer Science. 2023;1(4):67-80. (In Russ.) https://doi.org/10.26907/2949-3919.2023.4.67-80
Просмотров:
254
Послать статью по эл. почте 