0
$\begingroup$

I know exactly what a partially computable function is, but I've seen a few functions that I really can not understand why they are not partially computable. As an example in Davis book page 78, he says the following function is not partially computable: ($\uparrow$ means undefined and $\downarrow$ means defined)

Given an infinite set C such that $\phi(c,c) \uparrow$ for all $c \in C$ and such that

$$ H_4(x) = \begin{cases} 1 & IF \phi (x,x) \downarrow \\ 0 & x \in C \\ \uparrow & Otherwise \\ \end{cases} $$

is not partially computable.

Or in page 77 he says the following is partially computable while I cannot understand what is difference between these two functions!

Given an infinite set B such that $\phi(b,b) \uparrow$ for all $b \in B$ and such that

$$ H_3(x) = \begin{cases} 1 & IF \phi (x,x) \downarrow \\ 0 & x \in B \\ \uparrow & Otherwise \\ \end{cases} $$

Or between these two functions which one is partially computable? ($K=\{ n \in N | \phi(n,n) \downarrow \}$)

$$ f_1(x) = \begin{cases} 2 & x \in K \\ \uparrow & Otherwise \\ \end{cases} $$

$$ f_2(x) = \begin{cases} \uparrow & x \in K \\ 2 & Otherwise \\ \end{cases} $$

So I would like to know what makes a piecewise function to be partially computable?


UPDATE:

Since $K$ is recursively enumerable (in face m-complete), it is not recursive so checking membership in this set is semi decidable. I guess $f_2(x)$ should be partially computable but I'm not sure!

$\endgroup$
  • $\begingroup$ "I know exactly what a partially computable function is ... what makes a piecewise function to be partially computable?" -- contradiction? Note that these are exercises; you are to give $B$ and $C$ so that the same function (modulo a set parameter) is computable for one but not the other. $\endgroup$ – Raphael Feb 24 '15 at 22:46
  • $\begingroup$ @raphael I do not know this arrow notation. I suppose it means terminates or does not terminate, but which is which? $\endgroup$ – babou Feb 24 '15 at 23:21
  • $\begingroup$ @babou $\downarrow$ means termination, $\uparrow$ the opposite. $\endgroup$ – Raphael Feb 25 '15 at 7:08
  • $\begingroup$ @babou $\uparrow$ means undefined and $\downarrow$ means defined $\endgroup$ – No one Feb 26 '15 at 6:22
  • 1
    $\begingroup$ @Drupalist There is none. I'm not sure where your issue lies; it seems as if you have succumbed to a fundamental misunderstanding somewhere. $\endgroup$ – Raphael Feb 26 '15 at 8:16
1
$\begingroup$

A function $f : X \to Y$ is computable iff there is an algorithm that outputs $f(x)$ for every $x \in X$ after finite time. It's only partially computable if it does so for some $x$ but is undefined (i.e. the algorithm does not terminate) for the others¹.

As an example, consider the indicator function $\chi_A$ of some set $A$. $A$ is decidable iff $\chi_A$ is computable, semi-decidable (recursively enumerable) iff $\chi_A$ is partially computable, and neither if $\chi_A$ is not even partially computable.

So, in your first example, you have to determine for which infinite sets $A$ with $\Phi(a,a)\!\uparrow$ for all $a \in A$ the function

$\qquad\displaystyle H_A(x) = \begin{cases} 1, &\phi (x,x)\!\downarrow \\ 0, & x \in A \\ \uparrow & \text{ otherwise} \\ \end{cases}$

is partially computable. I assume that $\Phi$ is an enumeration of all partially computable functions, so $A$ is a set of indices of functions (TMs) that are undefined (don't terminate) on their own index. In other words, an infinite subset of $\overline{K}$, itself not semi-deciable.

$H_A$ is partially computable if and only if $A$ is semi-deciable.

In your second example, note that $K$ is the halting problem/language, $f_1 = 2 \chi_K$ and $f_2 = 2 \chi_{\overline{K}}$.

The rest is applying what you (should) already know, i.e. that $K$ is semi-decidable but $\overline{K}$ is not. That leaves a trivial reduction.


  1. Depending on your definition, "partially computable" may be the more general definition, i.e. "(totally) computable" is a special case.
$\endgroup$
  • $\begingroup$ So $f_2$ somehow equals to $\overline{K}$, right? so $f_2$ is not partially computable and $f_1$ is partially computable. right? $\endgroup$ – No one Feb 26 '15 at 8:34
  • 1
    $\begingroup$ @Drupalist "equals", no. Your conclusions seem sound, though. $\endgroup$ – Raphael Feb 26 '15 at 11:12
1
$\begingroup$

Page 3 of the book says: "partial function on a set S is a simply function whose domain is a subset of S."

The difference between $H_3(x)$ and $H_4(x)$ are the sets of $B$ and $C$ that you are going to make. for example if you give $B$ such that for all $x$ the other wise don't happen, then $H_3(x)$ will be a total function and we know every total functions are partial functions since $S \subseteq S$.

between $f_1(x)$ and $f_2(x)$ the one is partial computable which gives output for some $x$s in its domain.

$\endgroup$
  • $\begingroup$ So every partially computable function must have at least one output right? $K$ is r.e. (in fact it is m-complete) so checking membership in this set is not recursive (it is semi-decidable) so I guess $f_2$ is partially computable! I'm not sure $\endgroup$ – No one Feb 26 '15 at 7:56
  • $\begingroup$ @Drupalist , I guess not right! page 3 of the book mentioned that empty set itself is function. considered as a some partial function on some set S it is nowhere defined! I think I understood what make you confused. Did you want to know what functions are not partial? from what I know for all partial function we can construct a Turing Machine. for example we can use universal Turing machine for computing K (I mean we can use U TM to find out if x is in K ), but there is no Turing machine for computing K complement. $\endgroup$ – Doralisa Feb 26 '15 at 8:13
  • $\begingroup$ I guess $K complement$ problem is reduced to $f_2$ problem, and since $K complement$ is not R.E. so $f_2$ is not R.E. as well, is it true? $\endgroup$ – No one Feb 26 '15 at 8:35
  • 1
    $\begingroup$ @Drupalist , well I think so. whenever you could make a correct reduction between K complement and another set you can deduce the set is not r.e. $\endgroup$ – Doralisa Feb 26 '15 at 8:50

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.