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!
How to find out if a piecewise function is partially computable?
terminology;computability;semi decidability
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.Depending on your definition, partially computable may be the more general definition, i.e. (totally) computable is a special case.