2 papers
math.LO2022
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…
math.LO2021
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…