Undecidability of the degree structure of primitive recursive m-reducibility
Kalmurzayev B.S. Bazhenov N.A. Iskakov A.M.
1 June 2025Oxford University Press
Journal of Logic and Computation
2025#35Issue 4
Let Cmpr be the upper semilattice of degrees of computable sets with respect to primitive recursive m-reducibility. We prove that the first-order theory of Cmpr is hereditarily undecidable.
first-order theory , m-reducibility , primitive recursive function , undecidability
Text of the article Перейти на текст статьи
Kazakh-British Technical University, 59 Tole Bi Street, Almaty, 050000, Kazakhstan
Nazarbayev University, 53 Qabanbaybatyr Avenue, Astana, 010000, Kazakhstan
Kazakh-British Technical University
Nazarbayev University
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026