  Consider a decision problem whose instance is a function. Its degree of
undecidability, measured by the corresponding class of the arithmetic (or
Kleene-Mostowski) hierarchy hierarchy, may depend on whether the instance is a
partial recursive or a primitive recursive function. A similar situation
happens for results like Rice Theorem (which is false for primitive recursive
functions). Classical Recursion Theory deals mainly with the properties of
partial recursive functions. We study several natural decision problems related
to primitive recursive functions and characterise their degree of
undecidability. As an example, we show that, for primitive recursive functions,
the injectivity problem is Pi^0_1-complete while the surjectivity problem is
Pi_2-complete (omit superscripts from now on). We compare the degree of
undecidability (measured by the level in the arithmetic hierarchy) of several
primitive recursive decision problems with the corresponding problems of
classical Recursion Theory. For instance, the problem "does the codomain of a
function have exactly one element?" is Pi_1-complete for primitive recursive
functions and belongs to the class [Delta_2 - (Sigma_1 UNION Pi_1)] for partial
recursive functions. An important decision problem, "does a given primitive
recursive function have at least one zero?" is studied in detail.
