What is a totally defined partial recursive function?

Question

Alright, so I've always thought that a partial function was a function from $A$ to $B$ whose domain is only a subset of $A$. A total function, on the other hand, I took to be a function whose domain would be the whole of $A$ in the aforementioned case. So these two properties (i.e. partial vs. total) seemed mutually exclusive to me.

A recursive function, or so I supposed, is a function which is defined by a recursion equation (i.e. whose values are defined by previously defined values, etc).

Naturally then, I always thought that a partial recursive function was just a partial function that was defined by a recursion equation (i.e. previously defined values, etc.)

But now I'm being told that there are totally defined partial recursive functions?!? I tried to find some information on it, but all I found were a bunch of authors who just annoyingly assert this fact without further explanation. Example: "There are, of course, partial recursive functions that are totally defined..."

It seems like I'm missing something really simple here, someone please explain what I'm getting wrong.

Answer 1

The terminology in basic computability theory can be confusing at first. It works better to read "partial recursive function" as a single term. This class of functions is defined directly using some model of computation. (The term "recursive function" in computability theory is not directly about definitions by recursion; many models of computation do not have anything that corresponds to "recursion". The terminology is due to historical developments. In general "computable" and "recursive" are synonyms in this context.)

A "total recursive function" is then defined, later, as a "partial recursive function" which happens to be total. Many authors also use "recursive function" or "computable function" as a synonym for "total recursive function".

That terminology can give the misimpression that a "partial recursive function" is a "recursive function" which happens to be partial. The fact that "partial function" has its own meaning only encourages this misimpression. That kind of usage wouldn't make much sense, though, if the author uses "recursive function" to mean "total recursive function". The real state of affairs is that a "recursive function" is by definition a "partial recursive function" that happens to be total, and the term "partial recursive function" is defined before the term "recursive function" is defined, so the word "partial" is not just a modifier tacked on to "recursive function".

Some authors use the term "strictly partial" to describe a partial function that is not total. "Partial" on its own is neutral about whether a function is strictly partial or is total.

It would have been possible for authors to use "computable function" to mean partial computable function, and then they would need to explicitly say "total" when they want to assume the function is total. Instead, the convention is that "computable function" includes the assumption of totality, and when the author does not make that extra assumption, the term "partial computable function" is used. But even if they don't explicitly assume the function is total, "partial computable function" leaves open the possibility that the function is total.

Answer 2

There are rectangles that are squares, even though "most" rectangles aren't squares.

Similarly, a partial function from $A$ to $B$ is a function from $C$ to $B$, for some $C\subseteq A$.

Note that I wrote "$\subseteq$" and not "$\subset$" - $C$ is allowed to be all of $A$! (Some authors use "$\subset$" to mean "$\subseteq$," which I'd argue they shouldn't do. In this case, the same authors tend to use "$\subsetneq$" to mean "proper subset.")

Every total function is partial, but not every partial function is total!