Why is $x\mapsto x$-th prime number a partial recursive function?

213 Views Asked by At

I think that partial recursive functions correspond to all computable functions. Thus, if we can write a computer program to represent a function, the function is partial recursive.

In computability theory, primitive recursive functions are a class of functions that are defined using primitive recursion and composition as central operations and are a strict subset of the total $\mu$-recursive functions.

From another view, we show that the function $p_i$ yielding the $i$-th prime number is primitive recursive. and also we able to show that the predicate $\mathrm{Prime}(x)$ holding of prime numbers is primitive recursive.

My question is:

Why is $f(x)=x$-th prime number a partial recursive function?

I have seen and understood the most definitions but I just could not understand how to show this function is partial recursive or not?

1

There are 1 best solutions below

2
On BEST ANSWER

As André Nicolsas commented, all primitive recursive functions are total recursive -- and all total recursive functions are in particular partial recursive.

Here "partial" is the less demanding condition. A "partial recursive" function is allowed to but not required to be undefined for some inputs.