matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2024.2.47-69matatecs-44Research ArticleСТАТЬИПунктуальная категоричность и операция скачка в примитивно рекурсивных степеняхPunctual categoricity and a jump operation in the primitive recursive degreesКалимуллинИ. Ш.KalimullinI. Sh.

Искандер Шагитович Калимуллин, Кафедра алгебры и математической логики

ул. Кремлевская, д. 18, г. Казань, 420008

Iskander Shagitovich Kalimullin

Department of Algebra and Mathematical Logic

18 Kremlyovskaya str., Kazan 420008, Russi

Iskander.Kalimullin@kpfu.ruКурмачеваА. А.KurmachevaA. A.Александра Алексеевна Курмачева, Кафедра алгебры и математической логики

ул. Кремлевская, д. 18, г. Казань, 420008

Alexandra Alekseevna Kurmacheva 

Department of Algebra and Mathematical Logic

18 Kremlyovskaya str., Kazan 420008, Russia,

xsanca@mail.ruКазанский (Приволжский) федеральный университетРоссияKazan Federal UniversityRussian Federation202428072024224769Copyright © Калимуллин И.Ш., Курмачева А.А., 20242024Калимуллин И.Ш., Курмачева А.А.Kalimullin I.S., Kurmacheva A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/44

Статья посвящена изучению пунктуальных структур, для которых изоморфизмы между различными пунктуальными копиями примитивно рекурсивно сводятся к фиксированной 0, 1-значной оракульной функции. Для изучения сложности таких пунктуальных структур и изоморфизмов между ними вводится и исследуется операция слабого (0, 1-значного) скачка. В работе установлено существование жестких пунктуальных структур, для которых все изоморфмизмы являются низкими относительно слабого скачка и, при этом, не все из этих изоморфизмов примитивно рекурсивны. Кроме того, построена жесткая пунктуальная структура, для которой все изоморфизмы примитивно рекурсивно сводятся к слабому скачку нулевой функции, а один из них имеет высокую степень.

The paper is devoted to the study of punctual structures such that any isomorphism between any of its punctual copies is primitive recursively reducible to a fixed 0, 1-valued oracle function. To estimate the complexity of such punctual structures and isomorphisms between them we introduce and investigate the weak (0, 1-valued) jump operation. In the paper we establish that there is a rigid punctual structure for which all isomorphisms are low under the weak jump, and at least one of them is not primitive recursive. Also we construct a rigid punctual structure with every isomorphism reducible to the weak jump of the zero function, and with at least one having a high degree.

примитивно рекурсивная сводимостьпунктуальная категоричностьоперация скачкаprimitive recursive reducibilitypunctual categorcityjump operationThe work is supported by the grant of the «BASIS» Foundation. Also the results of the first paragraph were performed under the development program of Volga Region Mathematical Center (agreement no. 075-02-2024-1438).ReferencesD. 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-CD. 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-CD. 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-3D. 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-3I.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.029I.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.029N.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.20N.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И.Ш. Калимуллин, А.Г. Мельников, К.М. Нг, Различные версии категоричности без задержек, Алгебра и логика 56 (2), 256–256 (2017). DOI: https://doi.org/10.17377/alglog.2017.56.207I.S. Kalimullin, A.G. Melnikov, K.M. Ng, The diversity of categoricity without delay, Algebra Logic 56 (2), 171–177 (2017). DOI: https://doi.org/10.1007/s10469-017-9437-6E.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-4E.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-4I.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/S1995080221040107I.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Р.И. Соар, Вычислимо перечислимые множества и степени, Казан. матем. о-во, Казань, 2000.R.I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987. URL: https://link.springer.com/book/9783540666813S.C. Kleene, Extension of an eff ctively generated class of functions by enumeration, Colloq. Math. 6 (1), 68–78 (1958).S.C. Kleene, Extension of an eff ctively generated class of functions by enumeration, Colloq. Math. 6 (1), 68–78 (1958).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/2586811A. Urquhart, The complexity of decision procedures in relevance logic II, J. Symb. Log. 64 (4), 1774–1802 (1999). DOI: https://doi.org/10.2307/2586811S. Schmitz, Complexity hierarchies beyond elementary, ACM Trans. Comput. Theory, 8 (1), Article 3, 1–36 (2016). DOI: https://doi.org/10.1145/2858784S. Schmitz, Complexity hierarchies beyond elementary, ACM Trans. Comput. Theory, 8 (1), Article 3, 1–36 (2016). DOI: https://doi.org/10.1145/2858784W. 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.00120W. 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.00120J. 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.00121J. 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.00121L. 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.018L. 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

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