Which of the following is not primitive recursive, but partially recursive ?
Tripura Public Service Commission - 2019,
Answer: D
The function is the Ackermann function.
The Ackermann function is total and computable, so it is (partially) recursive in the sense of the general recursive or mu-recursive functions. But it grows faster than every primitive recursive function, so it cannot be built using only composition and primitive recursion. It is the standard example of a recursive function that is not primitive recursive.
The other names are not standard examples in computability theory, so they are ruled out.
Please log in or register to report this question.