As the title says; is this language decidable and how do you prove it?

$$L =\{\langle M\rangle \mid M \text{ is a Turing Machine and there is an input that } M \text{ halts on} \} $$

  • $\begingroup$ Turing machines are not decidable (or undecidable). Languages are decidable. $\endgroup$ – Yuval Filmus Aug 30 at 7:11
  • $\begingroup$ @YuvalFilmus: the title doesn't ask Is this Turing machine decidable?, but Is this Turing-Machine decidable?, and the pixel raster shows a language.) $\endgroup$ – greybeard Aug 30 at 7:14
  • $\begingroup$ thanks for noting. I'm a bit new to these definitions. $\endgroup$ – CompuPhisics Aug 30 at 7:48
  • $\begingroup$ It's not decidable. You could use Rice's Theorem to prove that. $\endgroup$ – plshelp Aug 30 at 12:22

Your language is not decidable. To show that it suffices to notice that the existence of a Turing machine $T$ that decided $L$ implies the existence of a Turing machine that solves the halting problem.

Indeed, given any Turing machine $M$ with input $x$ you can construct a Turing machine $M'$ that ignores its input, writes $x$ on the tape, and then simulates $M$. Clearly $M'$ halts (regardless of its input) if and only if $M$ halts on input $x$. We can decide whether $M'$ halts by checking whether $M' \in L$ using $T$ with input $M'$.

| cite | improve this answer | |

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.