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…