# 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, 2017 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. Oct 23, 2017 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. Oct 23, 2017 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.