I'm trying to show that the following are nonrecursive:
$\{x \in \mathbb{N} \mid \phi_x(y) \uparrow\}$
$\{(x,y) \in \mathbb{N}^2 \mid \phi_x = \phi_y\}$
$\{(x,y) \in \mathbb{N}^2 \mid y \in \operatorname{im}(\phi_x)\}$
$\{x \in \mathbb{N} \mid 0 \in \operatorname{im}(\phi_x)\}$
$\{x \in \mathbb{N} \mid \operatorname{im}(\phi_x)\mbox{ is infinite}\}$
So, to show a set is non-recursive, it boils down to showing that its characteristic function is non-recursive. Can someone explain how that helps in this case?
I do not know Rice's theorem yet, and for the first one:
1) Is the proof on page 102 of theorem 1.3 in Cultand sufficient?
2) Is this essentially the proof of theorem 1.5 in Cutland, page 104?
3) I don't see this in Cutland page 103-105
For 4 and 5, an someone provide a proof here? I am confused on the first few. Thanks
What are you allowed by way of background? If you are allowed to appeal to the industrial-strength Rice's Theorem, then things are easy. If you are having to work from closer to first principles then you've a lot of ground to cover.
Qn 1 is the halting problem (in very thin disguise), so you should already be able to answer this. [Shouldn't it be: is $\{(x, y) \in \mathbb{N}^2 \mid \phi_x(y)\!\uparrow\}$ recursive?]
Qn 2 is a bit tougher. Have a look at Cutland's classic book Computability where he proves this in a page-long proof on pp. 103-104. (Or see Carl Mummett's comment for a snappier argument).
Qn 3 is dealt with by Cutland on pp. 104-105.
(With the techniques we need for those first three questions mastered, you should be able to do the other two questions!)