What is a partially computable function?

In the book Computability, Complexity, and Languages, Martin Davis writes in chapter two:


A partial function is said to be partially computable if it is computed by some program.

and also


A function is said to be computable if it is both partially computable and total.

From the first definition, a partially computable function must be a partial function, but from the second definition a computable function must be partially computable and total which is a contradiction, because a function is partially computable if it is partial and a partial function can not be total at the same time!

The definition of partial function doesn't exclude the possibility that the function is total. On the contrary, every total function is a fortiori a partial function. Perhaps the terminology is unfortunate.

A function from $D$ to $R$ is a subset $f$ of $D \times R$ such that for all $d \in D$ there exists a unique $r \in R$ (denoted $f(d)$) such that $(d,r) \in f$. The domain of $f$ is $\operatorname{dom} f = D$.

A partial function from $D$ to $R$, where $\bot \notin R$, is a function $f$ from $D$ to $R \cup \{\bot\}$. When $f(d) = \bot$, we say that $f$ is undefined at $d$. The domain of $f$ is $\operatorname{dom} f = \{d \in D : f(d) \neq \bot\}$. If $\operatorname{dom} f = D$ then $f$ is total. For every partial function $f$, $f|_{\operatorname{dom} f}$ is a total function.

As you can see, a partial function is a function which can be undefined for some of the inputs; a total function is a partial function which happens to be defined everywhere.

Now regarding computability. Every program computes some partial function $f$ from $\mathbb{N}$ to $\mathbb{N}$; if the program doesn't halt on some input $x$, then $f$ is undefined on $x$, in other words, $f(x) = \bot$. A computable function is one computed by an algorithm which always halts.

StackExchange Computer Science Q#31981, answer score: 12