# 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!

• Note that other authors are very allergic to the term "partially computable function" precisely because it's like saying something is a "partially function". – Fizz Feb 25 '15 at 8:34

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.

• Here is a very important note that you pointed out: every total function is a fortiori a partial function Then how can you interpret the second definition of my question? A function is said to be computable if it is both partially computable and total. – No one Oct 16 '14 at 16:45
• See the last paragraph in my edited answer. Every program computes some partial function, which is undefined on inputs on which it doesn't halt. A computable function is a total function which is computed by some program. By definition, this program must always halt. – Yuval Filmus Oct 16 '14 at 17:38
• As a side note, it's a common confusion to think you can take a total computable function, restrict it to an arbitrary sub-domain and get a partial computable function. More on that at math.stackexchange.com/a/1133168/173347 Some authors prefer to say "computable partial function" instead because of this issue, but there are potential confusions with that terminology choice too. – Fizz Feb 25 '15 at 8:07