Problem Detail: 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!
Asked By : Drupalist
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/31981
