A={$i+1 | i \in N \varphi_i(1393)=2015 $} is Recursive?

Question

I see that my prof. wrote:

A={$i+1 | i \in N \varphi_i(1393)=2015 $} is Recursive, but B={$n^2 + n | n \in N \varphi_n(n)= \uparrow $ } is not an r.e set.

Who can learn me, about this two example?

Answer 1

Neither are recursive, by Rice's theorem: They are both equivalent to a non-trivial index set.

$A$ is r.e. because you can check whether $i+1 \in A$ by just running $\varphi_i(1393)$, wait for it to halt, and if it does check whether its output is $2015$.

$B$ is not r.e. because it's complement is r.e. and $B$ is not recursive. We can check whether $n \notin B$ by checking whether it is of the form $m^2 + m$, if it is not, we know $n\notin B$, and, if it is, run $\varphi_n(n)$ and wait for it to halt. If it does, we know $n\notin B$. This procedure correctly determines $n\notin B$ so $B^c$ is r.e.