# The set of turing machine that stops with input zero is not recursive

If M is a Turing Machine, consider the subset of $\mathbb{N}$ defined as: $$\mathrm{ZTM} = \{ x \mid M_x(0)\downarrow \}$$

i.e. the set of 'indexes' of machines that halt on zero. It is possible to use Rice's theorem to prove that this set is r.e. but not recursive.

But I'd like to have a direct proof, using directly some diagonalization argument if possible.

• Reduce from the halting problem. Do you know how to build a reduction? Have you tried coming up with a reduction? Can you find one? If you can find a reduction, you can combine that with the proof (by diagonalization) that the halting problem is not recursive to get a proof that your problem is not recursive either. – D.W. Oct 23 '17 at 15:36
• Yes, I know reductions. I agree that ones I have a working reduction it can be used to build a diagonal proof. To reduce from $H = \{ <M,w> | M(w) \downarrow \}$ I have to find a recursive $h$ such that $h(<M,w>) \in ZTM$ iff $<M,w> \in H$, but I was not able to find it. Since it seems that Rice apply, I tryied to reason about the proof of Rice, in some case it is done by an 'abstract' general reduction to HALT, but I was not able to adapt the same mechanism to this problem. Oh, I wanna also say that I'm not a student, only just reviewing some old TCS stuff. – Antonio Caruso Oct 23 '17 at 16:01
• It's easy to see that it's RE: just start simulating machines and output any that accept zero. But that's not what you're actually asking, so I edited the title. – David Richerby Oct 23 '17 at 16:06

Hint: if you want to know whether $M$ accepts $w$, build a machine that replaces its input with $w$ and then does whatever $M$ does.