Is $\{(x, y) \mid y \in \text{Range}(\phi_x)\}$ decidable?

Question

Is the following language decidable? A decidable language must be recursive, right? How should I show that the following is or is not recursive?

$$\{(x, y) \mid y \in \text{Range}(\phi_x)\}$$

Answer 1

Let $A$ denote the set above.

As usual, you can show that $A$ is not computable (recursive, decidable - all the same) if you can reduce it to a set that you know is not computable.

$K$ is a r.e. not computable set.

An equivalent characterization of r.e. sets, is that $B$ is r.e. if and only there is a total computable function $f$ such that the range of $f$ is $B$. This is in fact why r.e. sets are call recursively enumerable since $f(0)$, $f(1)$, $f(2)$, ... is a computable listing of $B$.

So since $K$ is r.e., there is a computable function $f$ such that the range of $f$ is $K$. Since $f$ is computable, it has an index $e$. That is, $f = \Phi_e$.

Then one has that $x \in K$ if and only if $x$ is in the range of $\Phi_x$ if and only if $(e,x) \in A$. This gives a many to one reduction of an incomputable set $K$ to $A$. So $A$ can not be computable.