Give a direct proof that the set $\{x|\Phi_x(1) \downarrow\}$ (which is a set of program numbers that halt on input $1$) is not recursive.
I've got an idea that indirect proof must work. Assuming that the set is recursive and ... But I have no idea how to go on from here.
The course source is Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science by Davis. So I'm familiar with notation used there and understand it better, if possible.
On
The following is not a (completely) formal proof, the reason is that there are many different model for computation and I don't not which one to choose. Anyway I'm pretty much confident that the argument can be easily applied in every model you choose.
For start let's remind that your set is recursive if and only if the predicate $\Phi_x(1)\downarrow$ is decidable.
The key for the proof is that the function which send every $n \in \mathbb N$ in the number representing the function
$$f(x) = \Phi_n(n)$$
is total recursive.
So for every $x \in \mathbb N$ we have that $$\Phi_{f(x)}(1) \downarrow \iff f(x)(1) = \Phi_x(x) \downarrow$$ so the predicate $\Phi_{f(x)}(1)\downarrow$ is equivalent to the predicate $\Phi_x(x)\downarrow$. Because $f$ is total recursive the predicate $\Phi_{f(x)}(1)\downarrow$ is decidable too. But we proved that this predicate is equivalent to the predicate $\Phi_x(x)\downarrow$ and so it should be decidable too but we know that this cannot be because of the halting problem.
Hope this help, feel free to ask if something is not clear.
Try reduce the problem to Halting problem ,
Halting problem: given M, Turing machine and input x,decide if M(x) halts .
so you want to find a computable functions that take instance of Halting problem and convert it to instance of this problem .