# Is it possible to obtain a total function by composition of partial functions?

This statement is Theorem 1.1 (page 39) of Computability, Complexity and languages by Martin Davis:

If function $h$ is obtained from the (partially) computable functions $f$, $g_1$, $g_2$, ..., $g_k$ by composition then $h$ is (partially) computable.

What I understand from this theorem is if there is at least one partial function among the composed function then $h$ is partial function. Am I right?

Here is an example, the functions $x$ and $x+y$ and $x.y$ are total but $x-y$ is a partial function. it is possible to obtain $4x^2-2x$ by composition of these functions in the following way, this function is total but it is obtained from an non-total function ($x-y$).

$2x = x+x$

$4x^2 = (2x)(2x)$

$4x^2-2x$          composition of $x-y$

This is an example from the book, is this example a contradiction of the theorem?

• Hint: $\mathrm{R} \subsetneq \mathrm{RE}$. – Raphael Oct 29 '14 at 6:50
• What is $R$ and $RE$ ? – No one Oct 29 '14 at 13:08
• The set of all total decidable and semi-decidable languages, respectively. (cf textbook definitions) I don't know if there's accepted standard notation for total recursive and recursive functions (I know T and P). – Raphael Oct 29 '14 at 14:01

The theorem should be read as "If you compose computable functions, you get a computable function; if you compose partial computable functions, you get a partial computable function."

Note that, perhaps confusingly, partial computable is a larger class of functions: every computable function is partial computable. One could reduce the confusion at the cost of verbiage by calling them total computable functions and partial-or-total computable functions. If you compose total computable functions, the result is a total computable function. If you compose partial-or-total computable functions, the result is a partial-or-total computable function.

Your example in the question shows that it's possible to combine a total function and a non-total function to get a total function. Notice that both examples actually only apply total functions directly to the inputs and at least one of the inputs to the non-total function is the output of a total function. In those circumstances, it's still possible to get a total function as the result of the composition. Conversely, if you apply a non-total function directly to your inputs (and none of its inputs is the output of some total function), your composition is guaranteed to be non-total.

• Is there any difference between the terminology of partial function and non total function? – No one Oct 29 '14 at 13:03
• @Mohammad A partial function might be total; a non-total function definitely isn't. – David Richerby Oct 29 '14 at 15:23
• in the above example composing a non total function leaded to obtaining a total function!\ – No one Oct 29 '14 at 17:24
• @Mohammad Composing total and non-total functions led to a total function. If you compose only non-total functions, the result must be non-total. – David Richerby Oct 29 '14 at 17:42
• @Mohammad If you compose non-total and total, it depends what functions you composed, yes. – David Richerby Oct 29 '14 at 18:37

This is a confusion about terminology:

• A function $f : A \to B$ is total if it is defined everywhere on $A$.
• A function $g : A \to B$ is partial if it is defined on a subset $A' \subseteq A$, called the domain of $g$.

Cruicially, there is no requirement that $A'$ be a proper subset of $A$. Thus, every total function is also a partial function.

This is common practice in mathematics. For instance, a square is also a rectangle, an equilateral triangle is also an isosceles triangle, a smooth function is also continuous, etc.