Recursive Set in Partial Computable Function Problem

Question

Suppose $A, B, C$ are disjoint set such as shown on this figure. $f_1(x), f_2(x), f_3(x)$ is partially computable function.

enter image description here

why $A,B,C$ is recursive set?

Every recursive set is in particular recursively enumerable. So if it is true that $A$, $B$ and $C$ are recursive, then the answer to "why not r.e?" is: "They are!" — hmakholm left over Monica, Jul 05 '14 at 11:57
in the above example we can say every partial computable function is recursive set? — user153695, Jul 05 '14 at 12:05
@ReneSchipperus: Things seem to make sense if $\uparrow$ means "undefined" (remember these are partial computable functions), and $\circ$ is taken to mean zero. If this is a scan from user153695's textbook, it has really awful typography... — hmakholm left over Monica, Jul 05 '14 at 12:14
i means can we say every partial computable function is recursive set? — user153695, Jul 05 '14 at 12:16
@user153695: You have written that comment several times. It doesn't make sense -- a partial computable function is a function, which is a different thing from a set (unless we're doing axiomatic set theory and identifying a function with its graph, but that's not what we're doing here). A partial computable function is a function and therefore not a set, and therefore, in particular, not a recursive set. — hmakholm left over Monica, Jul 05 '14 at 12:23
Even if we are considering a function to be the set ${(x,y)\mid f(x)=y}$ the set that represents an arbitrary partial recursive function is not a recursive set. A counterexample would be $$f(n)=\begin{cases} 1 & \text{program $n$ halts}\ \uparrow & \text{otherwise}\end{cases}$$ — hmakholm left over Monica, Jul 05 '14 at 12:25

score 1 · Answer 1 · answered Jul 05 '14 at 12:18

Run $f_1, f_2, f_3$ in parallel.

If $x \in A$ then $f_1(x) = 1$ and $f_3(x) = \circ$.
If $x \in B$ then $f_1(x) = 1$ and $f_2(x) = \circ$.
If $x \in C$ then $f_1(x) = 2$.
If $x \notin A \cup B \cup C$ then $f_2(x) = f_3(x) = \circ$.

Therefore after a finite amount of time you will be able to distinguish the four cases.

score 1 · Answer 2 · answered Jul 05 '14 at 12:21

Just write down what each of your $f_i$ functions does to each kind of input:

$$\begin{array}{r|ccc} x & f_1(x) & f_2(x) & f_3(x) \\ \hline \in A & 1 & \uparrow & 0 \\ \in B & 1 & 0 & \uparrow \\ \in C & 2 & \uparrow & \uparrow \\ \notin(A\cup B\cup C) & \uparrow & 0 & 0 \end{array} $$

So if you have an unknown input, just run all of $f_1$, $f_2$ and $f_3$ on it in parallel until either two of them have halted, or $f_1$ returns $2$. One of these will always happen, and what you know at that time will allow you to know exactly which line of the table you're in.

score 0 · Answer 3 · answered Jul 05 '14 at 12:20

Ok I am assuming the up arrow means that the computation diverges and that the tiny circle is a zero. All sets are recursive. From the functions we have enumerations of $C$ and $A\cup B$ (from $f_1$), enumerations of $\neg (A\cup C)$ and $\neg (B\cup C)$, the complements.

If $n$ is iin $A$ it will occur in the enumeration of $A\cup B$ and the enumeration of $\neg (B\cup C)$, all such common elements are in $A$. If $n$ is not in $A$ it will occur in the list of $C$ or $\neg (A\cup C)$.

A similar situation holds for $B$.

For $C$ if an element is in the list of $C$, then its in $C$, if $n$ is not in $C$ it occurs on one of the lists of $\neg (A\cup C)$ or $\neg (B\cup C)$.

Recursive Set in Partial Computable Function Problem

3 Answers3