6 papers · 1 filter
Primitive recursive categoricity spectra of functional structures
Nikolay Bazhenov, Heer Tern Koh, Keng Meng Ng
For the notion of degree of categoricity, we study an analogous notion for punctual structures. We show that such notions coincide for non--categorical injection structu…
Primitive recursive categoricity spectra
Nikolay Bazhenov, Heer Tern Koh, Keng Meng Ng
We study the primitive recursive analogue of computable categoricity spectra for various natural classes of structures. We show that these notions coincide for all relatively $Δ_{2…
Open Problems in Computability Theory and Descriptive Set Theory
George Barmpalias, Nikolay Bazhenov, Chi Tat Chong +11
These open problems were presented in the Problem Sessions held during the Tianyuan Workshop on Computability Theory and Descriptive Set Theory, June 16-20, 2025. The problems are…
Online and feasible presentability: from trees to modal algebras
Nikolay Bazhenov, Dariusz Kalociński, Michał Wrocławski
We investigate whether every computable member of a given class of structures admits a fully primitive recursive (also known as punctual) or fully P-TIME copy. A class with this pr…
Relatively acceptable notation
Nikolay Bazhenov, Dariusz Kalociński
Shapiro's notations for natural numbers, and the associated desideratum of acceptability - the property of a notation that all recursive functions are computable in it - is well-kn…
Intrinsic complexity of recursive functions on natural numbers with standard order
Nikolay Bazhenov, Dariusz Kalociński, Michał Wrocławski
Intrinsic complexity of a relation on a given computable structure is captured by the notion of its degree spectrum - the set of Turing degrees of images of the relation in all com…