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

Question

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?

Answer 1

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.

Answer 2

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.