4
$\begingroup$

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!

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – No one Oct 16 '14 at 16:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 16 '14 at 17:38
  • $\begingroup$ 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. $\endgroup$ – Fizz Feb 25 '15 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.