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.

  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Oct 23 '17 at 15:36
  • $\begingroup$ 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. $\endgroup$ – Antonio Caruso Oct 23 '17 at 16:01
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Sorry @David, I mixed up in the text the names of machines using always M, it is clear that you are not saying the same thing, since your M maybe are different or taken from different languages. Have you really followed completely your simulation argument? I tried in different way without being able to complete 'formally' the proof. $\endgroup$ – Antonio Caruso Oct 23 '17 at 16:32
  • $\begingroup$ Ok, I got from David the point. Given <H,w> I can build a program P = { H(w); if (w==0) return 1; }, then it stops in 0 if H(w) halt. so if I have a total recursive function for ZTM I can decide the halting problem. But, in some way I'm not satisfied, since this not helped in the original problem (the diagonal argument). $\endgroup$ – Antonio Caruso Oct 23 '17 at 16:43
  • $\begingroup$ Agreed, this doesn't do any direct diagonalization. From your comments below the question, I thought that you'd be OK with a reduction argument instead. Actually, I'm not sure that diagonalization is really possible, since there doesn't seem to be a "diagonal": the table of behaviours of Turing machines with empty input is essentially one-dimensional. $\endgroup$ – David Richerby Oct 23 '17 at 16:52
  • $\begingroup$ Yes, exactly, but I was surprised since I always looked at the reduction technique as a sort of 'less general way' with respect to build a diagonal proof. Usually it is also 'selled' in some textbook with an argument like: you don't need to show a proof by diagonalization all the time since we have this.., so it was, in a sense, implied that you can eventually find a diagonal argument all the time. But then, with the above language, the reduction (with your hint) at the end is not complicated, but the diagonal is not 'apparent'. $\endgroup$ – Antonio Caruso Oct 23 '17 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.