A partial function is called partial recursive if it can be computed by a Turing machine; that is, if there exists a Turing machine that accepts input x exactly when f(x) is defined, in which case it leaves the string f(x) on its tape upon acceptance.
By Church's thesis, a function is recursive if and only if it is computable.
| Rob van Glabbeek | rvg@cs.stanford.edu |