2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hint: $\mathrm{R} \subsetneq \mathrm{RE}$. $\endgroup$ – Raphael♦ Oct 29 '14 at 6:50
  • $\begingroup$ What is $R$ and $RE$ ? $\endgroup$ – M a m a D Oct 29 '14 at 13:08
  • $\begingroup$ 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). $\endgroup$ – Raphael♦ Oct 29 '14 at 14:01
8
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Is there any difference between the terminology of partial function and non total function? $\endgroup$ – M a m a D Oct 29 '14 at 13:03
  • 1
    $\begingroup$ @Mohammad A partial function might be total; a non-total function definitely isn't. $\endgroup$ – David Richerby Oct 29 '14 at 15:23
  • $\begingroup$ in the above example composing a non total function leaded to obtaining a total function!\ $\endgroup$ – M a m a D Oct 29 '14 at 17:24
  • $\begingroup$ @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. $\endgroup$ – David Richerby Oct 29 '14 at 17:42
  • 1
    $\begingroup$ @Mohammad If you compose non-total and total, it depends what functions you composed, yes. $\endgroup$ – David Richerby Oct 29 '14 at 18:37
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.