# How to find out if a piecewise function is partially computable?

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!

• "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. Commented Feb 24, 2015 at 22:46
• @raphael I do not know this arrow notation. I suppose it means terminates or does not terminate, but which is which? Commented Feb 24, 2015 at 23:21
• @babou $\downarrow$ means termination, $\uparrow$ the opposite. Commented Feb 25, 2015 at 7:08
• @babou $\uparrow$ means undefined and $\downarrow$ means defined Commented Feb 26, 2015 at 6:22
• @Drupalist There is none. I'm not sure where your issue lies; it seems as if you have succumbed to a fundamental misunderstanding somewhere. Commented Feb 26, 2015 at 8:16

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.
• So $f_2$ somehow equals to $\overline{K}$, right? so $f_2$ is not partially computable and $f_1$ is partially computable. right? Commented Feb 26, 2015 at 8:34
• @Drupalist "equals", no. Your conclusions seem sound, though. Commented Feb 26, 2015 at 11:12

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.

• 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 Commented Feb 26, 2015 at 7:56
• @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. Commented Feb 26, 2015 at 8:13
• 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? Commented Feb 26, 2015 at 8:35
• @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. Commented Feb 26, 2015 at 8:50