Undecidability of the degree structure of primitive recursive <i>m</i>-reducibility
Abstract Let $\mathbf{C}^{pr}_{m}$ be the upper semilattice of degrees of computable sets with respect to primitive recursive $m$-reducibility. We prove that the first-order theory of $\mathbf{C}^{pr}_{m}$ is hereditarily undecidable.
Authors
- Nikolay Bazhenov (ORCID: https://orcid.org/0000-0002-5834-2770)
- Alibek M Iskakov (ORCID: https://orcid.org/0009-0005-2550-2079)
- Birzhan Kalmurzayev
Institutions
- Kazakh-British Technical University (KZ)
- Nazarbayev University (KZ)
Publication Details
- Journal
- Journal of Logic and Computation
- Published
- 2024-11-08
- DOI
- https://doi.org/10.1093/logcom/exae074
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00