$L = \{ \langle M \rangle \mid \text{there is at least one input string on which the \(M\) does not halt} \}$

Here, for a Turing machine $M$, the notation $\langle M \rangle$ denotes an encoding, over some alphabet, of the code of the Turing machine. To which of the following language classes does $L$ belong?

  1. Regular.
  2. Context-free but not Regular.
  3. Recursive but not Context-free.
  4. Recursively enumerable but not recursive.
  5. Not recursively enumerable.
  • $\begingroup$ since it is given that M doesn't halt(i'm stuck here) if it is just that M "halts on some input x",then it is easy to say that it is regular,non-recusive..but it is given that M doesn't halt. $\endgroup$
    – Harshil
    Commented Sep 26, 2013 at 2:22
  • $\begingroup$ You're missing the point. The language is not the one accepted by $M$, but rather the one accepted by $L$. The question is, how hard is it to tell whether a given Turing machine halts on all inputs? $\endgroup$ Commented Sep 26, 2013 at 4:52

1 Answer 1


The language $L$ consists of (descriptions of) Turing machines $M$ such that $M$ does not halt on all inputs. In other words, $\langle M \rangle \notin L$ if $M$ halts on all inputs. Can you think of any connection to the halting problem?

  • $\begingroup$ i don't think any connection to halting problem $\endgroup$
    – Harshil
    Commented Sep 26, 2013 at 2:58
  • $\begingroup$ can u please elabroate ur answer i didn't get it!! $\endgroup$
    – Harshil
    Commented Sep 26, 2013 at 2:59
  • $\begingroup$ This is not an answer, but rather a hint. You will have to take it from here on your own. $\endgroup$ Commented Sep 26, 2013 at 4:01
  • $\begingroup$ for ur inteligency..._/\ _.... $\endgroup$
    – Harshil
    Commented Sep 26, 2013 at 4:41
  • $\begingroup$ @user561298 The language is defined in terms of whether Turing machines halt or not. Are you sure there's no connection with the halting problem? $\endgroup$ Commented Sep 26, 2013 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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