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

Question

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!

Answer 1

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.

Answer 2

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.