Пунктуальная категоричность и операция скачка в примитивно рекурсивных степенях
https://doi.org/10.26907/2949-3919.2024.2.47-69
Аннотация
Статья посвящена изучению пунктуальных структур, для которых изоморфизмы между различными пунктуальными копиями примитивно рекурсивно сводятся к фиксированной 0, 1-значной оракульной функции. Для изучения сложности таких пунктуальных структур и изоморфизмов между ними вводится и исследуется операция слабого (0, 1-значного) скачка. В работе установлено существование жестких пунктуальных структур, для которых все изоморфмизмы являются низкими относительно слабого скачка и, при этом, не все из этих изоморфизмов примитивно рекурсивны. Кроме того, построена жесткая пунктуальная структура, для которой все изоморфизмы примитивно рекурсивно сводятся к слабому скачку нулевой функции, а один из них имеет высокую степень.
Об авторах
И. Ш. Калимуллин
Казанский (Приволжский) федеральный университет
Россия
Россия
Искандер Шагитович Калимуллин, Кафедра алгебры и математической логики
ул. Кремлевская, д. 18, г. Казань, 420008
А. А. Курмачева
Казанский (Приволжский) федеральный университет
Россия
Александра Алексеевна Курмачева, Кафедра алгебры и математической логики
Россия
Александра Алексеевна Курмачева, Кафедра алгебры и математической логики
ул. Кремлевская, д. 18, г. Казань, 420008
Список литературы
1. D. Cenzer, J. Remmel, Polynomial-time abelian groups, Ann. Pure Appl. Log. 56 (1–3), 313–363 (1992). DOI: https://doi.org/10.1016/0168-0072(92)90076-C
2. D. Cenzer, R.G. Downey, J.B. Remmel, Z. Uddin, Space complexity of Abelian groups, Arch. Math. Log. 48 (1), 115–140 (2009). DOI: https://doi.org/10.1007/s00153-008-0113-3
3. I.Sh. Kalimullin, A.G. Melnikov, K.M. Ng, Algebraic structures computable without delay, Theoret. Comput. Sci. 674, 73–98 (2017). DOI: https://doi.org/10.1016/j.tcs.2017.01.029
4. N.A. Bazhenov, R.G. Downey, A.G. Melnikov, I.Sh. Kalimullin, Foundations of online structure theory, Bull. Symb. Log. 25 (2), 141–181 (2019). DOI: https://doi.org/10.1017/bsl.2019.20
5. И.Ш. Калимуллин, А.Г. Мельников, К.М. Нг, Различные версии категоричности без задержек, Алгебра и логика 56 (2), 256–256 (2017). DOI: https://doi.org/10.17377/alglog.2017.56.207
6. E.B. Fokina, I. Kalimullin, R. Miller, Degrees of categoricity of computable structures, Arch. Math. Log. 49 (1), 51–67 (2010). DOI: https://doi.org/10.1007/s00153-009-0160-4
7. I.Sh. Kalimullin, A.G. Melnikov, Punctual categoricity relative to a computable oracle, Lobachevskii J. Math. 42 (4), 735–742 (2021). DOI: https://doi.org/10.1134/S1995080221040107
8. Р.И. Соар, Вычислимо перечислимые множества и степени, Казан. матем. о-во, Казань, 2000.
9. S.C. Kleene, Extension of an eff ctively generated class of functions by enumeration, Colloq. Math. 6 (1), 68–78 (1958).
10. A. Urquhart, The complexity of decision procedures in relevance logic II, J. Symb. Log. 64 (4), 1774–1802 (1999). DOI: https://doi.org/10.2307/2586811
11. S. Schmitz, Complexity hierarchies beyond elementary, ACM Trans. Comput. Theory, 8 (1), Article 3, 1–36 (2016). DOI: https://doi.org/10.1145/2858784
12. W. Czerwin´ski, L. Orlikowski, Reachability in vector addition systems is Ackermann-complete, 2021 IEEE 62nd Annual symposium on foundations of computer science (FOCS), Denver, CO, USA, 1229–1240 (2022). DOI: https://doi.org/10.1109/FOCS52979.2021.00120
13. J. Leroux, The Reachability problem for Petri nets is not primitive recursive, 2021 IEEE 62nd Annual symposium on foundations of computer science (FOCS), Denver, CO, USA, 1241–1252 (2022). DOI: https://doi.org/10.1109/FOCS52979.2021.00121
14. L. Kristiansen, Information content and computational complexity of recursive sets, G¨odel ’96: Logical foundations of mathematics, computer science and physics – Kurt G¨odel’s legacy. Lecture Notes in Logic, 235–246 (1996). DOI: https://doi.org/10.1017/9781316716939.018
Рецензия
Для цитирования:
Калимуллин И.Ш., Курмачева А.А. Пунктуальная категоричность и операция скачка в примитивно рекурсивных степенях. Математика и теоретические компьютерные науки. 2024;2(2):47-69. https://doi.org/10.26907/2949-3919.2024.2.47-69
For citation:
Kalimullin I.Sh., Kurmacheva A.A. Punctual categoricity and a jump operation in the primitive recursive degrees. Mathematics and Theoretical Computer Science. 2024;2(2):47-69. (In Russ.) https://doi.org/10.26907/2949-3919.2024.2.47-69
Просмотров:
149
Послать статью по эл. почте 