  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 computable isomorphic copies of that structure.
We investigate the intrinsic complexity of unary total recursive functions on
nonnegative integers with standard order. According to existing results,
possible spectra of such functions include three sets consisting of precisely:
the computable degree, all c.e. degrees and all $\Delta_2$ degrees. These
results, however, fall far short of the full classification. In this paper, we
obtain a more complete picture by giving a few criteria for a function to have
intrinsic complexity equal to one of the three candidate sets of degrees. Our
investigations are based on the notion of block functions and a broader class
of quasi-block functions beyond which all functions of interest have intrinsic
complexity equal to the c.e. degrees. We also answer the questions raised by
Wright and Harrison-Trainor by showing that the division between computable,
c.e. and $\Delta_2$ degrees is insufficient in this context as there is a unary
total recursive function whose spectrum contains all c.e. degrees but is
strictly contained in the $\Delta_2$ degrees.

Logic