Can a recursive function be defined nowhere?

Question

I'm trying to show that a given function isn't recursive, so I assumed that it was recursive and composed it with a known recursive function to get back a function that is nowhere defined. However, I'm uncertain whether this is sufficient to conclude that the composition isn't recursive.

Answer 1

There's a somewhat unfortunate terminological issue here: Most books require recursive functions to be total.

To be specific, let's look at functions from natural numbers to natural numbers.

$\bullet$ A partial function is a function $\phi\colon A\to\mathbb N,$ where $A$ can be any subset of $\mathbb N.$

$\bullet$ A partial recursive function is a partial function $\phi$ that can be computed by some Turing machine; the Turing machine, when applied to some input $n,$ must halt iff $n$ is in the domain of $\phi$ (and, in that case, the Turing machine must compute the right answer, $\phi(n)$).

$\bullet$ A total function is a partial function whose domain is all of $\mathbb N.$

$\bullet$ A recursive function is a partial recursive function which happens to be total (that is, defined on all of $\mathbb N.$)

So, with these standard definitions, a recursive function has to be total.

Now, it looks like OP is actually using "recursive" to mean what's usually called "partial recursive." If that's so, then the method proposed will not work, since the empty function is a perfectly good partial recursive function.

If, in fact, OP did mean the standard definition of "recursive function", then the method proposed would be correct, since the empty function is not a recursive function (because it's not total). [But it seems doubtful to me that this method would be useful in practice, which is why I suspect that this isn't actually what OP meant. In a case where this method would seem to be applicable, it would probably be easier just to prove directly that the function in question wasn't total.]

Answer 2

Yes, the nowhere defined function is recursive. (As spaceisdarkgreen explained in the comments: consider the program that loops forever regardless of input.)

To illustrate the problem with your reasoning in another way: Let $f$ be any function which is not total. Pick a natural number $n$ such that $f(n)$ is not defined. Compose $f$ with the constant function $c(x)=n$. The resulting function $f(c(x))$ is nowhere defined. Can we conclude that $f$ is not recursive?